Waarmee navigeerde men voor de uitvinding van het kompas op zee?

Op basis van de sterren.

Toegevoegd na 1 minuut:
Om de lengtegraad te kunnen berekenen is het nodig om de tijd te bepalen. In de late middeleeuwen werd dit mogelijk met het nocturlabium. Dit instrument werkt alleen 's nachts, aangezien het de hoek meet tussen Polaris en een referentie-ster. Overdag is de tijd te bepalen met een zonnewijzer in combinatie met een kompas.

Volgens mij een sextant

Eerst met de octant.
Een octant dankt zijn naam aan de 1/8 cirkel van 360° = 45° die zijn gradenboog beslaat. De octant was tot 1767 in gebruik en werd daarna snel vervangen door de sextant.

Een sextant en octant zijn nautische navigatieinstrumenten waarmee de verticale hoek tussen een hemellichaam en de horizon wordt gemeten. Als de verticale hoek, de datum en het tijdstip van de dag bekend zijn, kan een hoogtelijn waarop men zich bevindt worden berekend.

Kijk hier voor meer informatie.
Ook voor een demonstratie van het gebruik.

http://nl.wikipedia.org/wiki/Sextant_(navigatie)

In de Hoge Middeleeuwen had men op zee geen navigatie-instrumenten. Men kon zich wat op de hemellichamen oriënteren maar zonder klok of sextant is dat vooral nattevingerwerk. Men probeerde dus meestal in het zicht van de kust te blijven, maar toch ging men gevaarlijker tochten niet uit de weg.
De Vikingen voeren naar IJsland en in de tiende eeuw zelfs naar Groenland en niet per ongeluk een enkele reis; men voer regelmatig heen en weer. Ook Ierse priesters (st. Brandaan) voeren die kant op om mensen te bekeren.
Als door bewolking de hemellichamen niet zichtbaar waren moest men zich verlaten op zeestromingen (voorzover bekend), wind, zeeijs, vogels of zelfs geuren. In een bekende ondiepe zee als de Noordzee kon men ook bodemmonsters nemen en aan de hand van het sediment ongeveer zien waar men was.

Er gaan verhalen dat de Vikingen een speciale zonnesteen zouden gebruiken om de positie van de zon te bepalen bij bewolkt weer. Lange tijd nam de wetenschap dit niet serieus, maar de laatste jaren wijst onderzoek uit dat dit toch wel eens zou kunnen kloppen. Zie link.