Before the advent of GPS, celestial navigation was the only way sailors could reliably determine their position when they were beyond sight of land. Today, celestial navigation continues to be practiced, both as a backup to satellite navigation, and because it's fun. (Of course, you may have a slightly different definition of fun.)
In a nutshell, you use a sextant to determine the angle between a celestial body (sun, moon, planet, star) and the sea horizon. By knowing this angle and the time, you can draw a line on the map where the observation took place (a line of position). By measuring the angle of several celestial bodies you can then draw several lines of position on the map, one for each celestial body. Where these lines of position intersect is where you are.
To be able to determine a line of position you need to know exactly where on earth, if you looked straight up, you would see that celestial body. This is called the "geographic position" (GP) of the celestial body. To determine this GP you need a clock and a Nautical Almanac (a book of the positions of celestial bodies as a function of time).
Finally, given the sextant angle and the GP of the celestial body, you can now compute the line of position. This process is called "sight reduction". It involves doing a little spherical trigonometry. You can do this either by table lookup (you need to carry a book of sight reduction tables) or by using a scientific calculator.
Sextants measure the angle between the sea horizon and a celestial body. These angles are measured in degrees and minutes of arc (1/60th of a degee). Measuring this angle to an accuracy of 1 minute of arc (1') will result in a positional accuracy of 1 nautical mile. Accurate sextants can measure this angle to an accuracy of 0.2'. This means that theoretically one can determine their position to 1/5 of a mile. Additionally, a good clock is required to accurately compute the GP of the celestial body. An error of 1 second in the clock will create a positional error of up to 1/4 of a mile.
A good navigator with an accurate sextant and clock can determine their position to within half a mile. Of course, if you're on a small boat that's bobbing around, you'd be happy to get to within a mile or two of the correct position.