New Zealand is named after Zeeland, a province in The Netherlands. How, and when it got this name is unclear.
Contratry to popular belief, New Zealand was not named by the first European discoverer Abel Janszoon Tasman (1642), a renowned Dutch navigator. Tasman named the country "Staten Landt", a name that was later changed to Zelandia Nova (as it appears on maps around 1643-1645); a reference to Zeeland*.
Tasman did name certain landmarks in NZ, e.g. Cape Maria van Diemen was named after the spouse of Anthony van Diemen; Governor General of Batavia.
And now I want a Steinie...
*ref: http://www.mapforum.com/9nz.htm