You can do it all with arithmetic: no algebra or trig. The Navy publications you saw are designed that way.
Starting with the Nautical Almanac: there are different treatments for the stars and for the Sun, Moon and planets. The stars are more or less fixed on the imaginary celestial sphere. They don't move in relation to one another. The Sun, Moon and planets do, so their use in celestial navigation is a little more complicated. The positions of the stars are specified in relation to the First Point of Aries (equivalent to the Prime Meridian) and a Celestial Equator (equivalent to Earth's equator.) That gives a way of locating each of the stars with just two numbers: sidereal hour angle (like west longitude) and declination (like latitude). Since they're in fixed positions on the celestial sphere while the Earth is rotating there must be a reference that tells where the first point of Aries is in relation to the Prime Meridian. That's why Aries has a column with the Sun, Moon and planets giving its GHA, its angular distance from the prime meridian, and the stars are located with respect to it.
With just the information in the daily tables and the time you can calculate the point on the Earth a star is directly above: its GP. The longitude of the GP is equal to the star's SHA, plus Aries' GHA. GP's latitude is equal to star's declination.
Using a sextant you can measure its altitude. Then your distance from the star's GP is 90 degrees minus that altitude. For example, if its altitude is 40 degrees, you're 50 degrees away from its GP. Each degree of arc is 60 nautical miles. So, if you had a globe and a compass you could draw a 3000 nautical mile radius circle on the globe and know your ship was somewhere on that circle at the time of the sight. If you have two star sights, the two positions where the circles intersect are two possible locations. With three sights there would only be one intersection for all three.
Drawing circles on a globe is nowhere near good enough for fixing position, but it's a good way to visualize the problem, and how it's solved. The other publications have tables for more accurate solutions. If I didn't make it clear enough above: the first Point of Aries only passes the Greenwich meridian about once a day as the Earth rotates inside the conceptual celestial sphere. It's distance is given by the GHA in the Aries column of the daily tables.
I'm surprised you saw the Air Almanac used on board ships. It was (is?) used on aircraft, and they necessarily have less accurate sextants - bubble sextants. They measure altitude with respect to a bubble like you'd see on a carpenter's spirit level, because much of the time the horizon isn't visible, and when it is, the dip correction depends on the aircraft's altitude which isn't as well-known as, say, the navigator's eye above sea level on the ship's O-5 level.