If you pick something in the heavens, whether it's the sun, the moon, a planet, or a star, you can think of it as being directly above some particular spot on the earth right this second.  A second from now, because the earth is turning, it will be directly above some other spot westwards on the earth.  Wait another second and that sun, moon, planet, or star will be directly above some other spot even further west on the earth, and so it goes second after second after second.  If you knew two things, you could tell where on earth you were.  Those two things are:

1. The celestial object was directly above you
2. What part of the earth the object was above at that exact time.

If you knew both those things, you'd know exactly where you were.  Unfortunately, if #1 is not true, you're kind of up the creek.  Ok, let's try something else then.  Let's assume that you knew these two things:

1. The celestial object was directly north (or south) of you
2. What part of the earth the object was directly above at that particular moment.

If you knew those two things, you'd know that you were at the same longitude as the celestial object.  You'd know your longitude, but not your latitude.  At least it's halfway there.  You could, in this instance, simply sail east or west until you're at the same longitude as your destination, then sail due north or south until you bumped into your destination.  It would be crude, but it would work.  All you would need for this, actually, is a very very good watch.  You know that the sun (for example) passes directly south of Greenwich England (0 degrees latitude) at exactly noon then.  Because the earth turns 360 degrees in 24 hours, you know that it turns 15 degrees every hour.  If you know how long after it passes Greenwich until it passes you, then multiply that by 15, you'd know your exact longitude!  Let's try that...

You have a watch that is 100% accurate and is set to UTC (formerly known as Greenwich Mean Time).  By your watch, the sun passes due south of you at 18:30 (we use 24 hour time to make the calculations easier!).  Since noon at Greenwich is 12:00, we subtract 12:00 from 18:30 (the time it passes us) and we get 6:30.   So, the earth turned for 6 hours and 30 minutes until the sun passes us.  Changing the minutes to a fraction, it passes us 6 and 1/2 hours after it passed Greenwich.  Multiply that by 15 and we get 97.5 degrees WEST longitude.  We're at 97.5W.  If we could only get our latitude, we'd know exactly where we are.

And, of course, we can.

If we were directly under the sun, the sun would be at 90 degrees angle above the horizon (that's the definition of "directly overhead").  However, for most of the year it will not pass directly overhead at noon, and some places it will never pass directly overhead (for example, here in Canada, the sun is always somewhat south of us).  By knowing the difference between directly overhead and the actual angle of the sun, we can calculate how far north or south of the spot directly under the sun we are.  This is where the navigation instrument called the sextant comes in to play.

A sextant is just a fancy instrument for measuring an angle.  In celestial navigation, we simply use it to measure the angle from the horizon.  For instance, we might measure that the sun is 45 degrees above the horizon.  Using that information and something called an "ephemeris", plus a whole bunch of other tables that take into account how high above sea level our eye is, the amount of "bend" that light takes going through the atmosphere, etc., we can calculate how far north or south of that spot we are and what that spot is for this day of the year.

And from that, we can figure out our latitude.

So to get our latitude and longitude we need:

• Sextant
• Very very good watch
• Ephemeris
• "Sight reduction tables"

None if which requires satellites nor electricity.  Of course, with the various satellite navigation systems, that's what most people use and, to be honest, it's a lot more accurate than using sextant, watch, and tables.  However, doing celestial navigation is kind of like sailing.  For boating, a power boat will get you to your destination faster and more easily than a sailboat, but a sailboat has magic.  GPS will be far more accurate and is easier and doesn't take practice, but celestial navigation has magic, not to mention a deep connection with the past of sea faring.