In 1642 the Dutch explorer Abel Janszoon Tasman (who today is immortalised in the name of Tasmania) and his crew were (probably) the first Europeans to see the islands that are now known as New Zealand. At the time it was hypothesized that there was a 'Great South Land' to "balance" the land masses in the Northern hemisphere which appears on maps as some variant of Terra Incognita Australis - see this 1570 map for instance.

Tasman believed that he had reached part of this extensive continent. 26 years before this, other Dutch explorers had sighted land to their south while near the tip of South America and similarly believed it to be part of the Great Southern Land. They called this place Staten Landt. Tasman believed that the land that he had discovered was connected to Staten Land as in the map I linked to above and so did not given his land a new name. It is sometimes claimed that he called it Nieuw Zeeland, which is incorrect. Shortly afterwards someone else rounded Staten Land in the Tierra del Fuego and proved that it was just a island, smaller than Delaware and had no connection to the land Tasman had found 5000 miles away. Staten Land became known as Staten Island, and today it is part of Argentina.

So now they needed to come up with a new name for the land Tasman had found (or possibly the decision not to prejudge the question of whether the two landmasses were linked was taken before this). In 1645 some anonymous cartographer (possibly Johan Blaeu) baptised it Nova Zeelandia, Latin for Nieuw Zeeland or Zealande. Zeeland is the second largest province of the Netherlands. It is not known precisely why the new name was chosen. I have seen it suggested that this was in tribute to investors in the Dutch East India company who had sponsored Tasman's voyage, or by analogy with the name for the territory now known as Australia, which the Dutch called New Holland after the other major Dutch province. There was also a New Zealand in the Dutch Caribbean. When Captain Cook arrived more than a century later and claimed the land for the British Crown he did bother to change the name, labelling it on his map as 'New Zeland'.