Vodafone have service in both AU and NZ, and I believe they do offer some travel sim card covering both countries. You can look for a Vodafone reseller at MEL and ask.

However most likely the cheapest options will be to get a different SIM for AU and NZ. If any AU SIM works in NZ it will be at a price premium.

You can also look into international travel SIM cards, which may be available online, offering reasonable rates in multiple countries.