NavList:

Much of this is from memory but the answer to your survey part is "With a lot of work." The same as with all old surveys. In most cases a land survey was by triangulation and from several "known" points surveys go out in multiple directions to converge on previously unknown points and the surveyor must resolve any errors. In one old history I read they described setting up a plane (flat) table with a  telescope mounted on a straightedge. This was set up at one point and directions were extended and drawn to multiple visible points. Then the plane table was set up at a known second point and the lines drawn again. Then, ideally a third known point. From the distances and direction between the "known" points, the lines should cross at the unknowns and define their locations. You worked your way up the river like this. (Perhaps defining some new "known" points occasionally?)

So, the "known" starting points? These were easier on land and usually depended on celestial sights. The missing link back then was time and lunars or  transit of Jupiter's moons were ways to get exact time in pre-chronometers days. Once you got a known point, sun, and other, sights could confirm your times. (I'm not 100% confident here but, with latitude and time, would the sun define longitude to survey standards?)

Celestial sights could also give you true direction when declination was unknown. Any inaccuracies in your land based sight equipment could be averaged out by taking multiple sights.

It's easy to overlook the work that went into most maps.