I don’t know the details of how they did the Mason-Dixon, or indeed historical american surveys but here’s a bit of my conjecture on how they did it. Several of the elements of it have been touched on already.
The first problem was to decide where the boundary was defined from. From Wikipedia, it seems like the definition decided on was “the line of latitude 15 miles south of the southernmost house in Philadelphia.” Once the house was decided on, finding a point 15 miles to the south of it would have been a relatively easy survey that could have been done through a few methods available at the time. So they’d have surveyed south and marked the 15mi south point with some sort of block.
The next task would have been to work out the latitude and longitude of the block. This would have been done using observations to the stars, a relatively new technique at the time. Wouldn’t have been too different from navigation of a ship, but the need for higher accuracy would mean that they’d have to use more stable instruments and do multiple measurements so that a single error didn’t throw the whole lot off.
Having determined ‘where they were’ they would have also oriented their instruments using the stars, aligned the telescope of their instrument due west, and sent their assistants to cut a line through the wilderness so that they could get a line of sight to the next point they wanted to mark. They would have had to have been very careful due to the long distance, and would have had to adjust the way the instrument was facing due to the curvature of the earth, etc.
Because there was no fixed point at the other end to check onto , they would have had to ‘daisy chain’ a series of segments, making sure each one was correct before continuing. (and indeed, the wiki article notes the line is actually a series of segments).
For each segment, they would have required a way of checking that they had got things right, and they must have had two ways of doing that - either they would have surveyed back to the start of the segment and compared the position calculated through the survey work to the position of the start of segment, or they could have surveyed from the start of segment to the next major marker and then check their position astronomically. Certainly, when they got to the end point, they would have used astro observations to check their work.
For the minor markers, because the distances were smaller, they might have got away with simply putting them directly in line between the major markers, simply set up on one of the markers, align the telescope with the next one, chain out the distance to the one you want to put in, and get the guy putting in the new marker to walk north or south until he gets right on the line that you are looking down. (but doing it all very carefully! Fucking up a state boundary line is not good for future business!)
Because all this is a hassle (seems like Mason and Dixon took about 5 years to do it?) between about 100 and 200 years ago most major powers started work on various survey systems where the local surveyors could start from a nearby benchmark instead of calculating their position the hard way. The Public lands system and the Great trigonometrical survey already mentioned are examples of the two major approaches to this.
Local surveys used many of the techniques already mentioned, they used more theodolite and chain and less astro and trig. The way properties used to be surveyed used to follow a more rigid pattern because that meant less computing trig by hand. They used to survey directly along boundary lines more because there were less immovable obstacles (You can’t rip down someone’s fence to see along the line anymore) and less/easier field calculations involved.