Du måste inte ha något tillstånd, men beroende på rutt vill du nog skaffa ett DOC hutpass för access till alla stugor som inte är på en Great Walk. Finns att köpa på DOCs kontor i Auckland, öppet vardagar. Det är främst för längre perioder, men jag har för mig att 6 månader bara kostade typ 400 spänn.
Tältning behöver ni inget tillstånd till på DOCs marker, men om ni är på privata områden ska ni fråga markägaren om lov och naturreservat kan ha särskilda regler.
Se till att särskilja er som trampers när ni pratar med markägare, med till exempel vandringsstavar. Trampers är populärare än konventionella backpackers.
EDIT: Det brukar normalt gå bra att stealthcampa, men som sagt är det ofta onödigt då markägaren ändå ofta ger tillstånd. Då slipper man också få tältet upprivet av en arg bonde på morgonen, utan kanske blir bjuden på frukost av samma bonde istället.
EDIT2: Har ni tänkt över det här att ni gör vandringen mitt i vintern? Sydön är seriöst jobbig vid den tiden på året och nordön har också rätt kasst väder.