Dead reckoning (DR) navigation was the way early mariners deduced their speed. In the days before the invention of celestial navigation DR was an essential tool for plotting a ship's global position when out of site of land. Christopher Columbus used this method on his early voyages, although celestial navigation was, by then, coming into its own.
The use of the compass for navigation began in Europe in the late 12th Century, but the only way to work out the distance travelled was by knowing the speed of the ship. Only then could a map be charted with any degree of accuracy.
Distance travelled is the product of speed and time. Time was measured with an hour glass before the invention of an accurate chronometer, and every hour a piece of flotsam, usually a log tied to a length of rope knotted at regular intervals, was thrown overboard. The speed of travel was calculated from number of knots which were pulled into the sea in the specific time marked by the hour glass (To this day, nautical miles per hour are still measured in knots). Once the distance was calculated and the compass bearings noted, the progress of the ship could be plotted on the chart.
In emergency situations, such as when there is a failure of electronic navigation equipment, DR is still used today. This method, if performed carefully, can achieve around 90% accuracy.
http://www1.minn.net/~keithp/dr.htm
http://www.jsc.nasa.gov/er/seh/navigate.htm