The Mercator projection (1536) must be great for nautical navigation. It allows one to find a bearing and keeping this constant one should reach the target (if not in the shortest line). But how did people navigate before this? As an example Magellan circumnavigated the globe ca. 1520.
There are a variety of ways to navigate across oceans without the aid of maps and in particular the Mercator Projection. It is worth noting that before the invention of the chronometer (calculation of longitude) in 1764 there wasn't a reliable way of measuring longitude when out-of-sight of land.
Most of the history I have read includes the Mediterranean Sea where navigation would, in ancient times, either take place along coastal routes or through celestial navigation (following stars) to navigate across open ocean. One of these longer routes is the famous voyage of Nearcho from India to Susa after Alexander's campaigns into India. It is worth noting that there is eveidence of charting and the intriguing Antikythera mechanism that will have aided ancient Greek peoples in the Mediterranean Sea.
In Northern Europe Viking tribes used stones (Iceland Spar) to locate the sun in the sky when it was obstructed from view (very helpful in Northern Europe) to aid with following the sun across open water.
Some early navigational tools include:
- Mariner's Compass
- Portolan Chart's that include only a compass rose to indicate bearing
- Jacob's Staff
One of the keystone methods is dead-reckoning. This is where the navigator finds their position by measuring course and direction. You start from a known location and using a compass measure bearing and taking into account speed, through measuring knots on a rope, pin where you are most likely to be (two men would work with one running and counting the number of knots that pass whilst another turns a sand-timer, thus calculating how far you have travelling in a set amount of time). Of course this is easily erroneous, but it's the best you can do until the chronometer and GPS came about :-).
The above tools would have been available to sailors during the 15th-16th Century (upto 1536) and mainly helped in accessing your latitude (i.e. the angle of Polaris).
Before the publication Christopher Columbus (1492) "discovered" America, Vasco da Gama voyaged round Africa to India (1498), and Ferdinand Magellan's voyage (1522) circumnavigated the Earth, navigation was primitive but functional, although I believe through a bit of luck a lot was accomplished.
Navigation would have been through a combination of the tools above and due to other environmental variables such as using known prevailing wind directions and signs of land.
Have a look at the The Age of Reconnaissance he does a thorough examination of Navigation.
Simple answer? They didn't really.
Their routes are mostly coast-hopping. When they left the known coasts (i.e. crossing non-contiguous continents), they really hadn't a clue where they were. Latitude was OK with a star chart, but longitude was impossible until the chronometer was invented. Dead reckoning runs out of accuracy pretty quickly, and fails completely in bad weather.
Remember that Columbus thought he'd hit India (hence "West Indies" and "native American Indians"), which gives you some idea of the state of navigation at the time. Magellan followed Da Gama's route across the Atlantic, but Da Gama hadn't a clue where he was either. Magellan coast-hopped round South America until he reached about the same latitude as he started (which is something he could tell from stars), at which point he just went due east and hoped he ran into land before he ran out of food and water.
The Polynesians observed and learned a star catalog of declination and right ascension--This allowed them to ( a ) identify and name a navigation course, ( b ) transmit it orally to another navigator, ( c ) follow such a course.
My understanding is that they learned "chains"--a chain is a sequence of stars that rise at approximately the same angle away from the observed celestial pole (either North or South) The chain is characterized by ( i ) angular deviation from the pole, and ( ii ) phase correspondence to day of the year and time of night.
Island locations in the ocean can be discovered because it reflects ocean swells in rings concentric with the island. A navigator familiar with the major swells can follow a (reflected) cross-swell directly towards such an island.
This wikipedia article mentions these, and gives a much fuller description. https://en.wikipedia.org/wiki/Polynesian_navigation