How animals guide themselves across vast expanses of open ocean, sometimes to specific geographic areas, has remained an enduring mystery of behavioral biology. In this review we briefly contrast underwater oceanic navigation with terrestrial navigation and summarize the advantages and constraints of different approaches used to analyze animal navigation in the sea. In addition, we highlight studies and techniques that have begun to unravel the sensory cues that underlie navigation in sea turtles, salmon and other ocean migrants. Environmental signals of importance include geomagnetic, chemical and hydrodynamic cues, perhaps supplemented in some cases by celestial cues or other sources of information that remain to be discovered. An interesting similarity between sea turtles and salmon is that both have been hypothesized to complete long-distance reproductive migrations using navigational systems composed of two different suites of mechanisms that function sequentially over different spatial scales. The basic organization of navigation in these two groups of animals may be functionally similar, and perhaps also representative of other long-distance ocean navigators.