Hau-Maka had a dream in which his spirit traveled to a far country, to help look for new land for King Hotu Matu'a. He traveled to the Mata ki te rangi ('Eyes that look to the sky). The island has also been called "Te pito o te henua", which means "the Center of the Earth." Both islands are commonly said to be Easter Island.
When Hau-Maka woke, he told the King. The King then ordered seven men to travel to the island from Hiva, their mythical home, to investigate. They found the land and returned to Hiva. The king himself then traveled to the new island.
Hotu Matu'a led his people from Hiva; linguistic analysis comparing Rapanui to other Polynesian languages suggests this was the Marquesas Islands.
From Nova Travel's article on the History of Easter Island:
Hotu Matu'a was the first highest rank leader of Easter Island. According to the legends, the Ariki Mau, Hotu Matu'a arrived from an island or group of islands called Hiva; apparently a catastrophe had sunk their land.
Other source(s): http://pvs.kcc.hawaii.edu/ike/moolelo/hotu_matua.html