I agree with what Lynn says , except for the bit about the North Island :) (since I live there).
For fantastic moderate tramping check out the Great Walks, although booking is often required (for a price), and camping can be limited. I've listed some other trips below to consider as well.
Since you are in NZ during March to November remember that is autumn to spring here. The best months are definitely March through to May, then October-November. In the South Island unless you like snow, thats probably your lot. In the North Island, there is much less snow, however the there still is the same amount of water falling out of the sky, so you'll need to deal with lots of rain and mud.
The tramping hut network in NZ is awesome, most huts apart from the high-end serviced huts are $6/night and provide great shelter from the storms that often blow through. the huts usually have some sort of fire, and bunks/sleeping platforms with mattresses, and a water supply. You can get a 6 month hut pass that allows unlimited use of the huts for about $90, so if you are planning on more than 15 nights use of huts then it's a bargain.
Along with what Lynn has already suggested and the Great Walks, in the North Island consider:
- a 3-4 day loop through Whirinaki Forest Park
- Mt Taranaki Round the Mountain track
- Either loops including Sunrise hut or Rangaiwahia hut in the Ruahine Forest Park
- ANYTHING in the Tararua Forest Park but especially Holdsworth/Jumbo loop, any of the northern, middle or southern crossings, and from Otaki Forks a loop along the Main Range taking in a climb to Kime, along the ridge, over the Tararua Peaks to Maungahuka, keep following the ridge to Junction Knob then down to Waitewaewae, then back following the river to Otaki Forks. This trip over 4-5 days would certainly give you a grounding in the variety of NZ tramping in the birthplace of trmpaing in NZ.
In the South Island consider:
- Queen Charlotte Walkway
- combining the Heaphy with the Wangapeka Track
- Follow the Te Araroa Route through the Richmond Range
- The Sabine/Travers loop through Nelson Lakes NP with side trips to Blue lake and Lake Angelus
- the Matukituki valley with side trips in Mt Aspiring NP
- the Hollyford
Along with these longer trips there are so many moderate trips of 2-3 days that I just don't have time to write about here. As pointed above, you can live in NZ all your life and only scratch the surface with whats available.
Some other places for info:
website of the govternment department responsible for looking after the national and forest parks.
NZ forum for trampers.
Also there are plenty of books with lists of trips. 101 great tramps, X marks the spot are two that come to mind.
If you have any more questions just ask away.