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?
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:
The key to reaching Rapa Nui would be to get enough days of favorable westerly winds ... to come close enough to the island to see it, or detect it indirectly by telltale cloud formations, by the appearance of terns or other 'land finding' birds, or by other signs by which island navigators use to recognize when land is near.
He speculates that perhaps
some especially adventurous voyagers [went] down to around 35° South to try to run before westerlies there, and that after a week or two the cold wind and rough seas forced them to angle north to seek the warmth of the tropics. If so, they might have stumbled across Rapa Nui in their flight from the cold.
Another possibility is that
Marquesans sailing to the Tuamotus could have been driven far to the east by sudden westerly gales, and then have elected to keep heading in that direction in hope of finding land sooner than it would take them to work their way back to the west. Similarly, people making a crossing from Mangareva to Pitcairn, or between islands in the Austral group might have been driven far past their target by strong westerlies and then opted to keep pressing eastward.
The article goes into a lot more detail, and also has links to diaries of the Hokule'a expedition to Easter Island.
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.
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.
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.
The idea that reaching distant islands would be difficult or impossible for "primitive" peoples is something commonly believed by city dwellers inexperienced with ocean sailing. If you go to Bath or Newport and start hanging out with the old timers there, they can quickly disabuse you of the notion that sailing to Rapa Nui is impossible. In fact, if you watch Robert Redford's recent movie "All is Lost" you can see him sailing thousands of miles completely alone in a relatively small vessel, and then doing hundreds more in a life raft. Vikings routinely rowed and sailed thousands of miles in the treacherous North Sea, loaded down with weapons no less.
After World War II, a Scandinavian adventurer named Thor Heyerdahl specifically set out to show a few men with only the most primitive of equipment could explore the breadth of the oceans. In 1947, he captured the public imagination with his Kon Tiki expedition, going from South America to the Polynesian islands in an oversized raft. He wrote a series a books on his findings. If you read these books, it should resolve any questions you may have about the abilities of ancient mariners.
Kon Tiki vessel in 1947.
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).