Hi Justin,
I assume you already validated webmaster tools for all three domains. Generating the sitemap: it depends a bit on the situation. I guess you have only 1 site (the .com.nz version) and that you point the .com & .com.au to this version. In that case, it's probably difficult to generate the xml for the other version via the CMS you are using. What you could do is, on a regular basis (e.g. once/week) copy the existing sitemap & do a simple find/replace of the .com.nz & then save the sitemap as sitemap_us.xml & sitemap_au.xml. In webmaster tools you delete for the .com & .com.au the current entry & replace it by the correct version.
The sitemap just helps google to find the url's on your site - so don't expect miracles from it, as Google is perfectly able to crawl your site & find all the url's.
On the longer term, it's probably better to create multiple versions of your site to fully adapt to local requirements (the prices are listed in NZD & I guess English in NZ is more related to British than to American English).
Hope this helps,
Dirk