The idea of using a lodestone to magnetize an iron needle, which when rested of a piece of straw and floated in a bowl of water, would point to the north, came from the Chinese, and came into use in Europe at the latter end of the first millennium.
In the early 14th century a card was attached to the needle, and marked off in compass points, so the navigator could steer a course by it. This must have been as stupendous an innovation to the old ship-pilots as GPS is to us today.
The earliest charts that we know of are the Portolan charts. The name derived from Portulano, a book of sailing directions produced by the Venetian and Genoese navigators in the 14th and 15th centuries. These were really more pictorial than accurate. They were made on papyrus or on lambskin, and were colorfully marked with a drawing of the coast and the various towns marked on it. The wind directions were marked on them, using what was known as a ‘wind rose’. With the increasing use of the compass, this became the compass rose.
By the 15th Century, mariners had learned how to calculate their latitude, by measuring the angle between the Pole Star and the horizon. To do this they used the mariner’s astrolabe. This instrument was a simpler version of a more complex one, used by Muslim astronomers for hundreds of years. But that’s another story.