Islands leave distinctive cloud formations in their wake, sometimes stretching many hundreds of miles. Here's an example from satellite photography: http://m.earthobservatory.nasa.gov/NaturalHazards/view.php?i...
A popular theory is that Polynesian navigators would hone in on these cloud patterns in the sky, treating them as the big arrows in the sky pointing to land that they essentially are.