There are three main networks.
http://www.spark.co.nz/shop/mobile.html
http://www.vodafone.co.nz/mobile/
http://www.2degreesmobile.co.nz/home * (2 degrees runs their own networks in the major urban areas (they say 97% of the population) but use vodafone's network when outside of their own network)
The other mobile companies are basically resellers of these three.
2 Degrees is cheapest for ongoing costs but may have less 4g coverage (it's expanding), but they are all much of a muchness. I run Spark because it's a work phone, my girlfriend uses 2degrees because its cheaper, I haven't noticed a difference between them.
As far as phones your probably best to buy here, that way you know the phone will work with the network. If you buy in Canada you will need to make sure that the radio frequencies that the phone supports are compatible with one of the NZ networks.
Phones are generally unlocked so you can buy say an iphone from apple or another network and run it on your network, otherwise you can get discounts for signing up to a contract, or you can get a termless contract and buy the phone for full price.