New Zealand was settled by Polynesian voyagers over a period extending from about AD 800 to 1300. They had no written language, as far as anyone knows, but had and still have a rich oral tradition where eveyone learned about his or her ancestry.
In 1642 a Dutch expedition under Abel Tasman "discovered" the country, mapping some of its west coast. The country's current name is an Anglicised version of a name Dutch cartographers applied to it. Tasman's name is applied to a few features such as a large bay (one of the earliest he visited) and a glacier (which he was never near).
The next visit from Europeans was much more detailed. In 1769, after observing a Transit of Venus from Tahiti, Englishman James Cook brought his expedition south on the strength of secret Government orders to look for southern lands to colonise. Sailing west, he reached the Gisborne area and ended up circumnavigating the whole country and encouraging his scientists to make detailed studies of flora and fauna. He claimed it for Britain. His name is commemorated in the highest mountaintop, the strait between the two main islands, and a number of other places.
Whalers and sealers were the main visitors over the next few decades. In the early 19th century, Europeans brought to the natives a variety of new things such as Christianity, writing, disease, and muskets, and a few traders set up trading posts or became farmers.
In 1840, the same year as some planned settlements (e.g. Wellington) took place, the Treaty of Waitangi was signed between the representatives of Queen Victoria of Great Britain (just 4 days before her wedding) and leaders of the Maori people, who were given the status and protection of British subjects in return for officially allowing the British to settle and to buy land and to govern. Debate about what the Maori signatories thought they were giving away remains a great talking-point, but relations between the races are more amicable in New Zealand than in most colonised countries. Extensive intermarriage continues.
British government systems led to such institutions as censuses and the registration of births, marriages, and deaths, very like the systems that were developing in Britain in the mid-19th century. The early registrations were, as in Britain, a bit short on detail from a genealogy viewpoint, but later that century more details were added to the requirements.