There are several useful threads in the Australia/NZ Travel forum.
<font face="Verdana, Arial, Helvetica, sans-serif" size="2">Originally posted by Globaliser:
A standard GSM phone (anything that works in Europe/Asia etc.) will be fine for both Australia and NZ.</font>
You can also rent a phone from Vodafone at the airport on arrival.