I used an agency when we moved out as i also work within an area which trains very few nurese. I used Healthlink and a woman called Lee saw me through all the various steps l needed to cross prior to NZ registration as well as helping me with my immigration paperwork. She was able to offer a few DHB's with openings and l eventually interviewed with 2 of them, choosing eventually to settle in Dunedin.
Although Healthlink are based in Auckland, they appeared to have contacts with all or most of the DHB's and had valuable local information on the 2 areas l looked into. All the assisstance from Lee was either online or via the phone (at their expense!!).
When l arrived l had 2 weeks free accomadation (prior to starting work) and they also paid my airfare. Think some DHB's may offer better relocation terms if you approach them directly but as the agency took all the stress out of the application process l was more than happy with my lot!.
Good luck
Karen