The concept of celestial navigation is actually pretty simple. Actually doing it requires physical skill.
The general idea is this. Take for example the star Altair, at any given instant it is directly above exactly one spot on Earth. If you were at that spot and measured it's elevation above the horizon, it would be 90 degrees. That point is called the "Geographic Position (GP)". So, if you were at some unknown location and measured Altair to be 45 degrees, you would know you were 45 degrees from Altair's GP, and all of the points satisfying that can be plotted as a circle on a map. Repeat that for another star and you end up with two circles that intersects at two points. You could repeat with a third star, but in practice you have a rough idea of where you should be, and you choose stars that produce a large enough circle that you can disregard one of the two points. And taking that "in practice" one step further, the diameters of the circles are so large, you really just need to draw part of the circle as a straight line, and that lets you plot in a small enough area that map distortions are of no significance (unless your very close to the poles). There's a standard form called a "VP-OS" which makes the process a lot easier. A video showing how to do it is [1].
To determine the GP of a star (or planet) you need an ephemeris of some sort, there's software to do it, but a copy of the Nautical Almanac provides enough information to make the process simple enough to do with paper and pencil.
Actually measuring the elevation of a star on a moving, bobbing ship is where the real skill comes in. At the equator, being off by one degree means your result will be off by about 60 miles. Skilled navigators can fix their position within a few hundred feet!
[1] https://www.youtube.com/watch?v=bVIPorb_aMM