Everybody has a different position.
Mine, and was advised by NZ house in London, was to simply get on a plane with a tourist visa and find a job. Once here with a job offer, applying for a 2 year work permit was dead easy.
Just out of interest, what does the girlfriend do?
Teacher or a nurse and they will roll out the red carpet. Truck drivers not so much but if you have additional skills like forklift or swing lift cranes, it will help you massively.
Thought about a holiday? Rent a camper and have a drive around, talk to people. See what you can find. I sold everything I owned and came out here to start again without ever being here before, Austrailia is a short hop and was my second choice if NZ didnt work out for me, but the overwhelming factor was get out of UK.
What I did do before, was to read up. Find out as much as I could about the place and decide what and where would suit me best.
That was Hawkes bay. And 15 years later, I am still here.
The weather is awesome. And on the note, am going to play on my jetski while it’s still holidays.