One of the best ways to change the default search engine is with a free plugin called Inquisitor. You can find it at http://www.inquisitorx.com/safari/index_en.php (note beta versions for Firefox and Internet Explorer also).

Download the zipped file and double-click it to unzip. Make sure that you have quit Safari, then double click on the installer package as you see below...

Go through the installer process as you see in the image below...

Once installed, start Safari, go to the "Safari" menu and choose "Preferences"...

You'll now notice a new button in the tool bar of Safari preferences (the dark icon you see being clicked in the image below)...

In the window that appears, you can select "Google New Zealand" from the pop-up menu, or a multitude of other search engines....

If you have issues with the plugin, information on how to uninstall it can be found here http://www.inquisitorx.com/faq.php