This is very much related to your phone and to a certain extent your provider. It is especially important for Verizon customers because their network is different to most of the world (CDMA vs. GSM) and hence the phones they sold often only worked on their network, unless they were marketed as 'world phones'. You should also consider the frequencies supported (Verizon and T-Mobile use different frequency bands to most of the world).
In this case though, the iPhone 5s is a 'world phone'. Looking at the specs (http://www.apple.com/iphone-5s/specs/),
Model A1533 (GSM): UMTS/HSPA+/DC-HSDPA (850, 900, 1700/2100, 1900, 2100 MHz); GSM/EDGE (850, 900, 1800, 1900 MHz); LTE (Bands 1, 2, 3, 4, 5, 8, 13, 17, 19, 20, 25)
Model A1533 (CDMA): CDMA EV-DO Rev. A and Rev. B (800, 1700/2100, 1900, 2100 MHz); UMTS/HSPA+/DC-HSDPA (850, 900, 1700/2100, 1900, 2100 MHz); GSM/EDGE (850, 900, 1800, 1900 MHz); LTE (Bands 1, 2, 3, 4, 5, 8, 13, 17, 19, 20, 25)
Model A1453: CDMA EV-DO Rev. A and Rev. B (800, 1700/2100, 1900, 2100 MHz); UMTS/HSPA+/DC-HSDPA (850, 900, 1700/2100, 1900, 2100 MHz); GSM/EDGE (850, 900, 1800, 1900 MHz); LTE (Bands 1, 2, 3, 4, 5, 8, 13, 17, 18, 19, 20, 25, 26)
Model A1457: UMTS/HSPA+/DC-HSDPA (850, 900, 1900, 2100 MHz); GSM/EDGE (850, 900, 1800, 1900 MHz); LTE (Bands 1, 2, 3, 5, 7, 8, 20)
Model A1530: UMTS/HSPA+/DC-HSDPA (850, 900, 1900, 2100 MHz); GSM/EDGE (850, 900, 1800, 1900 MHz); FDD-LTE (Bands 1, 2, 3, 5, 7, 8, 20); TD-LTE (Bands 38, 39, 40)
... you can see that the CDMA version (model A1533 - you should be able to confirm this in Settings>General>About>Model) supports UMTS/HSPA+ (the 3G technologies in use in NZ) and GSM/EDGE (the 2G technologies in use in NZ).
The frequencies in use in NZ are -
2 Degrees (http://en.wikipedia.org/wiki/2degrees#Network) -
3G (UMTS) - 2100 Mhz (urban) and 900 Mhz (rural)
2G (GSM/EDGE) - 900 Mhz and 1800 Mhz
Vodafone (http://en.wikipedia.org/wiki/Vodafone_New_Zealand#Coverage) -
4G (LTE) - 1800 Mhz
3G (UMTS) - 2100 Mhz (urban) and 900 Mhz (rural)
2G (GSM/EDGE) - 900 Mhz and 1800 Mhz
Telecom NZ (http://en.wikipedia.org/wiki/XT_Mobile_Network) -
4G (LTE) - 1800 Mhz
3G (UMTS/HSPA+) 2100 Mhz (urban) and 850 Mhz (rural)
The frequencies match up to the ones supported on your iPhone, so therefore you should be fine on any of the mobile networks and you should get at least 3G data performance in urban areas, if not 4G. You might fall back to 2G on some networks outside urban areas.
Verizon has also previously stated that they do not carrier-lock the SIM slot on iPhones, so you should be free to use other SIM cards abroad (see http://9to5mac.com/2012/09/24/verizon-iphone-5-wont-ever-be-locked-most-likely-due-to-the-fcc/, but do check with them first though).
Finally, do consider the T-Mobile global roaming option, however I believe that only allows you to roam for 3 out of the previous 6 months or something like that, to prevent people from signing up and permanently using it abroad. I don't have any recommendations as to which network you should sign up for, but note that the 2 degrees network is only available within urban areas; outside urban areas, it falls back on to the Vodafone network and you may lose data access (although calling and SMS should be fine).
