Pp. 539-542 of volume 10-1 of Gauss's werke include entry 97 in Gauss's diary:
I have found new exact formulas for the parallax of the Moon.
as well as the formulas themselves (which were rather found in a different place than Gauss's diary) and an excerpt from his 1799 letter to the Prussian cartographer Karl Ludwig von Lecoq who was assisted by Gauss in his trigonometric survey of Westphalia. It is not a well known fact, but Gauss's first astronomical activity was done in this context (this was two years before his calculation of Ceres orbit), and Lecoq wrote in his "report on the trigonometric survey of Westphalia" that "In the astronomical part of the survey, the calculations of Gauss were of great help to me". It seems that determining the exact geographic location of points by means of astronomical observations was quite a common procedure in the 18th century.
I have not included Gauss's formulas here (the formulas are quite complicated) since I want to understand more about the context of the "lunar parallax problem" and not to immerse myself immediately in the mathematical details. I know that the ancient Greek astronomer Hipparchus used a kind of lunar parallax calculation during a solar eclipse in order to determine the distance to the Moon (he did it by comparing the details of the total eclipse and the partial eclipse observed in two cities whose distance was known). But I don't understand how it is possible that a complete description of the lunar parallax was not established yet in the end of the 18th century (if it was well calculated then I don't think that Lecoq should have needed Gauss's help), a time when spherical trigonometry was quite ripe and a lot of data was collected on the Moon's orbital parameters.
Also, I'm not sure I understand the complexity of this problem - Parallax in general is the angular shift in observed position of a distant object when the observer changes his location; so the description of the lunar parallax angle $\alpha$ seems to me to be very simple - $\mathbb{tan\alpha} = \frac{2R_E}{d}$ (here $R_E$ is the Earth radius and $d$ the Earth - Moon distance).
So I would like to understand what meanings were attached to the notion of lunar parallax in the 18th century, and to understand what was the main difficulty in the related problems.
Update
I now understand that determining the lunar parallax was crucial for exact calculations of the observer's geographic location - especially in surveys of "small regions" in global terms (such as Westphalia) where the accuracy needed is much higher (I guess the accuracy needed is 10's or 100's times higher than in more global surveys). This is because the change in observed lunar position consists of the change in zenith direction (of the earthly observer) and the parallactic change due to the change in observer location. That is, when an observer changes his earthly location he can deduce his geographic location directly from the change in the background of fixed stars, but if he uses the Moon as a reference (which is much closer to us than fixed stars) he has to remember that the change in observed lunar position is not only the result of his zenith rotation but also of the Moon's parallax.
Therefore, to avoid errors one has to separate the parallax part from the first part in order to determine the change in zenith direction (which amounts to determining geographic location). I don't know why 18th century surveys had to use the Moon instead of some fixed stars, but in any case, if one uses the Moon, they are led to an interesting geometric problem.
Although the magnitude of parallax correction $\pi '$ can be easily determined by observing the Moon altitude $a$ - as in terry-s's answer, it satisfies the equation $\mathbb{sin} (\pi ') = \mathbb{cos}(a) \cdot \mathbb{sin}(\pi) = \mathbb{cos}(a) \cdot (\frac{R_E}{d})$ (sine theorem in euclidean trigonometry) - determining the direction in which the parallax correction should be applied (in order to find the exact direction of observer's zenith) seems to much more complicated as it depends on the lunar declination (which changes from 18 to 28 degrees and back during a month), the hour angle, as well as the observer's latitude and longitude.
Thus, in terms of data obtained by observing the Moon's position in the sky, the direction of parallax correction seems to be a complicated function of the Moon's altitude and azimuth as well as the timing of the observation, so determining the observer's latitude $\theta$ and longitude $\varphi$ by this method turns into a complicated trigonometric equation in unknowns $\theta,\varphi$ and coefficients that depend on the lunar position (azimuth, altitude and day of the month). This explains the apparent complexity of Gauss's formulas.
Question
Apart from deciphering Gauss's formulas, I also fail to understand why cartographers needed to use the Moon's position (a process that is prone to complexities) instead of using some fixed stars? Is it just because the Moon is the simplest celestial body to find at night?