http://www.celestialnavigation.net/astro.html and at Henning Umland's, A Short Guide to Celestial Navigation. http://home.t-online.de/home/h.umland/ In part, modern navigation is complicated mathematics.
Ancient celestial navigation http://www.celestialnavigation.net/history.html had to be much more simple than that, but not that much is known about the navigation used in distant prehistoric periods.
The following is a seminal source for an understanding of ancient navigation:
Navigation in the Ancient Eastern Mediterranean - Thesis by Danny Lee Davis of Texas A&M University, which can be downloaded as a .pdf of 21.58 MB (some pages unfortunately sloppily scanned), at http://nautarch.tamu.edu/pdf-files/Davis-MA2001.pdf. This is an absolutely new and essential work in this field, especially chapter V "Night-Time Navigation and Celestial Aids" and Chapter VI Ancient Navigational Systems: A Synthesis of the Evidence (p.186) including the Section "Imagining Ancient Systems of Navigation: A View from Antiquity: The Neolithic System".
Davis writes among other things about "star-path" sailing. This method of sailing steers directly by the stars, keeping the vessel directed toward a particular star and changing the star used as stars change their positions over time. Davis writes - correctly in our opinion - that this may explain the depiction of particular stars above the bows or sterns of ships on ancient reliefs.
Davis also writes about ancient navigation as follows:
"Crete is believed to have been colonized by migrant farmers from Anatolia as early as the eighth or seventh millennium B.C., although hunter-gatherers surely landed there earlier. Broodbank and Strasser have shown that the colonization of this island must have been deliberate and that a minimum number of people and livestock were required to sustain its initial population. From what we know of visibility and the limitations of paddled craft, this colonization and its maintenance are a further indication that a navigation system embracing celestial observation was in place this early. The colonization of many other Aegean island and Cyprus in the Final Neolithic serves also to indicate a high level of navigational confidence -- and one that must have entailed the usage of some system of reference for sailing at night, if only the circumpolar stars for orientation." (pp. 145-146)Other sources on celestial navigation are:
Traditional Navigation in the Western Pacific
showing navigation by rising and setting stars
Gary Agranat - Astronomy: Time and Navigation (links)
Peter Ifland, in The History of the Sextant
http://www.mat.uc.pt/~helios/Mestre/Novemb00/H61iflan.htm discusses how the North Celestial Pole (currently the star Polaris) can be used to determined latitude and how the Arabs later used the kamal, see http://snipurl.com/brqd for this purpose, employing also their fingers (issabah) for measurement. Ifland also explains the concept of "shooting the stars". Take a look at that. Ifland is the author of Taking the Stars: Celestial Navigation from Argonauts to Astronauts. http://www.amazon.co.uk/exec/obidos/ASIN/1575240955/
Peter Tyson - Secrets of Ancient Navigation
John Davis - Seaman's Secrets
Cogswell and Schiøtz - Navigation in the Information Age: Potential Use of GIS for Sustainability and Self-Determination in Hawai'i
E.G. R. Taylor - The Haven-Finding Art: A History of Navigation from Odysseus to Captain Cook, published by Hollis & Carter,London, for the Institute of Navigation, 1956.
See also http://www.celestialnavigation.net/haven.htm.
Charles H. Cotter - A History of Nautical Astronomy, William Clowes and Sons, London
Charles H. Cotter - The Complete Nautical Astronomer
Nick Strobel - Astronomy Notes
and History of Astronomy
Heavenly Mathematics: Cultural Astronomy
The Mariners Museum
The Gilbertese Skydome. Polynesian and Micronesian Astronomy
Crichton E.M. Miller - Ancient Navigation
Ancient Navigation Techniques
Ancient Discovery Before Christ
The Etruscan Bronze Liver of Piacenza