The only GSM operator in NZ is Vodaphone, so if you want to buy a GSM sim for NZ that's your sole option. There are stores and dealers all over the place and you can look up locations on the Vodaphone website:

http://www.vodafone.co.nz/

Since Vodaphone has a monopoly on GSM in NZ, the phones they sell aren't locked (seeing as there's no other NZ network they could be used on anyway). If you don't have or forgot to bring an unlocked GSM phone with you to NZ, you can also usually pick up a basic Vodaphone GSM phone + SIM for around $100 - $120 NZ at some dealers like Dick Smith Electronics. The phone will be unlocked and also comes with the advantage of having the right AC adapter/charger for NZ.