Easter Island is extremely remote, being thousands of kilometers from its nearest neighbor. How did people get there safely, and how did they even know it was there?
OK, extremely crazy theory here, but is it possible that they just walked? If you take a look at this satellite view it looks as if Easter Island was the highest peak of a mountain range that is no longer above the sea level. However, in order for that to have occured, this "peak path" should either be extremely shallow (no way to easily verify right now), or that happened many thousands of years ago (at least if we take into account the evolution of the sea level over time).
According to this page, Rapa Nui's latitude is -28, almost -30. That is a border between zones of prevailing eastern winds (to the North from -30) and prevailing western winds (to the South), according to the map.
Another point is that the navigation of the Polinesians was a right-angle one. They sailed first along the meridian (by polar star or Southern cross or Sun (by measuring 90 degrees from the sunrise point with correction for the latitude), up to the known parallel. Afterwards they sailed along parallel (by measuring the height of the Polar star or the Sun.) Alternatively, they sailed first along the known parallel up to the known island and after that along the meridian. So they solved the problem of longitude measurements, even though they never measured it.
Such navigation was possible for them, because when the wind was not in their back, they simply rowed and didn't change their course due to the wind. They didn't change their course because of the style of their navigation, not because they were not able to change the course. Obviously, they strongly preferred the wind to their back.
So, if somebody wanted to return back from the islands to America and was to the South of the Equator, he should go down to -30. This would be out of the zone of eastern winds, to its border, where the sailing to the East became easier and could easily go along the parallel. Of course, according to the season, it could be parallel a pair of degrees to the North or to the South of -30. So, finding Rapa-Nui, which was so close to the "magical" wind border, was inevitable.
If somebody, as in the legend that Rose mentioned, wanted to find some new country, sailing from America, where would he sail? Of course, along the southern edge of the area of eastern winds, because all areas to the North were already checked. Also, the desert -25-30 parallels were the best candidates for such a search. Again, the find was very probable.
So, it seems that finding Rapa Nui was much less random than the finding of most other islands in the Pacific.
One more possibility is that they voluntary checked all parallels with some methodic process, going further and further to the south. This would explain the find of New Zealand, too.
As to how they made it safely, don't be fooled by the fact that they only had 'canoes'; double-hulled ships are far more seaworthy than single hulls of a similar size.
That's not to say it wasn't risky or difficult, but modern people have successfully followed the paths of early Polynesian migrations using traditionally designed boats and (more impressively, imho) traditional navigation techniques. Ben Finney wrote a book about his experiences in Hokule'a, a double-hulled canoe which later (in 1999) made the voyage to Easter Island.
How they decided to make that first trip, without knowing for sure that an island was there, is a more interesting question. Rapa Nui (Easter Island) tradition says that a king dreamt of the island's existence and ordered an expedition to find it. You don't have to be woo to believe that something like that might have actually happened - after centuries of sailing eastward and settling new islands, the idea of trying it again wouldn't have seemed all that outrageous. Anything from overpopulation to a ruler showing off for a girl could have led to such an order being given.
Obviously no one knows for sure what happened, but I found an article in which Finney explains the difficulties the first expedition would have faced, not least of which is the primarily easterly winds in that part of the Pacific. A sailing vessel can actually sail against the wind by zigzagging, but it's difficult and greatly increases the distance of the journey. Therefore, Finney says:
He speculates that perhaps
Another possibility is that
The article goes into a lot more detail, and also has links to diaries of the Hokule'a expedition to Easter Island.
I don't know how Easter Island was first discovered, but returning to it after discovery was done by celestial navigation. For each latitude on Earth their are certain key stars that pass directly overhead at that latitude. Thus, knowing the celestial latitude of key stars meant that one could find his own latitude. The navigators would sail due North / South (also by way of celestial navigation, though this is more difficult in the southern hemisphere due to the lack of a pole star) to the desired latitude, then turn west or east to get to the island in question.
Polynesians discovered and colonized pretty much the entire Pacific this way. Easter Island is one of their more impressive discoveries, but it isn't even the most impressive. That title has to go to Madagascar, which was settled from Borneo (about 5,000 miles away!).
How did they do this? Well, the Polynesians were the ancient world's best navigators, and had developed all kinds of techniques. One thing not many of us land-lubbers think about is migratory birds. They can't fly forever, so islands they can stop and rest at are important to them. They don't just flap around the ocean aimlessly looking for islands when they get tired; they fly straight from island to island. Therefore an ancient navigator knows he must eventually find land if he just follows the trail of migratory birds.
One other thing to note. Sweet Potatoes were domesticated in (mainland) South America. However, they somehow appeared in New Guinea (and got added to the standard diet) about 1200 years ago. That's 8,000 miles away. How did this happen? There are some wacky one-in-a-million theories running around, but the most likely explanation is that there was some small amount of interaction (perhaps even trade) going on between Polynesians and South Americans as far back as 800 CE.