For the hundreds of years till the mid-19th century, vessel speed at sea was measured using a chip log. The chip log was a wooden board attached to a logline wound on a reel so the user can easily reel it out.
The log-line had knots at uniform intervals (47.3ft) and the Wooden board weighted enough to float perpendicularly to the water surface and thus present substantial resistance to the water moving around it.
Chip log or Ship log (Wikipedia)
To measure speed a sailor would through the wooden board of the stern and began to count the number of paid-out knots. At the same time, another sailor would use a 30-second sand-glass to measure time.
Once they had the distance and the time, speed was just a question of easy math.