Celestial navigation from scratch Is it possible to establish one's longitude and latitude by observing the stars? Can you use observations of the stars to find the relative distance between two locations, which would be useful in map-making? What kind of crude tools would help (a sextant is too complex, but maybe a backstaff?)

What difference would there be if you were doing this on a planet that was not the Earth, and had a different location in the galaxy, a different day and year length?
To expand a little on James's answer: The pole angle method doesn't care what time of year it is, the celestial pole isn't going anywhere. ;) However, if you're in the tropics, the altitude of the celestial pole is rather low, which can make accurate observation difficult.

Of course, if you're doing this on another planet, (or even in Earth's southern hemisphere) you may not have a convenient pole star, and doing this sort of thing without decent equipment isn't going to be particularly accurate.

To determine longitude you need to have a good way of determining the time relative to a fixed reference, like the Greenwich meridian. The Earth makes one rotation on its axis (relative to the stars) in a (sidereal) day, so one day is equivalent to 360° of longitude, one hour corresponds to 15°, and one minute of time corresponds to 15 minutes of longitude, which is 15 nautical miles at the equator, and around 11.5 nautical miles at 40° latitude. In other words, if your time calculations are off by one minute, your position calculations can be off by 10 to 15 miles.

Newton described a method of determining the time from the moon, you can read about it in Wikipedia's Lunar distance (navigation) article. From the Earth, the Moon's angular diameter is roughly 0.5°, and it takes roughly an hour for it to travel through that distance relative to the stars. So if you want time measurements accurate to the minute you need very good observations. However, that's the easy part.

You also need very accurate calculations that tell you where the Moon's supposed to be at that point in time. And that's not easy to do - the Moon's motion is tricky! I won't go into the details here, but Wikipedia has a good introduction to lunar theory. If you're curious about the kind of formulas that get used, take a look at the links in this question.

So it wasn't just the difficulty of making sufficiently accurate shipboard observations that prevented Newton's method from being adopted, it was also the difficulty of preparing sufficiently accurate lunar tables. Actually, Newton's method of lunar distances was used, principally from 1763 (when the necessary tables and method were first published) until about 1850, when it was superseded by the marine chronometer. However, as Wikipedia mentions, 


  The method saw usage all the way up to the beginning of the 20th
  century on smaller vessels that could not afford a chronometer or had
  to rely on the this technique for correction of the chronometer.
  [...]
  Captain Joshua Slocum, in making the first solo circumnavigation in
  1895–1898, somewhat anachronistically used the lunar method along with
  dead reckoning in his navigation.


To quote Captain Slocum:


  Even expert lunarians are considered as doing clever work when they
  average within eight miles of the truth.


Of course, on another planet you may have a better-behaved moon, or no moon at all. Or, as James mentioned, you may be very lucky and have a nearby large planet with fast-moving moons that are visible to the naked eye.