How did they do this?

It's a matter of joining the dots. For example, to draw the shape of a coastline on a map, start with measurements of the latitude and longitude of a set of points along the coastline, mark those on your map, and draw a line connecting them. The accuracy will depend on (a) how many points you have and (b) how accurately the latitude and longitude are measured.

Latitude is relatively easy - just measure the maximum angle of the sun above the horizon; this and the date give you the latitude. You can also measure the angular height of stars above the horizon.

Longitude is much harder - you essentially have to measure the difference in local time (as observed from the motion of the sun) and the time at your reference zero longitude. Even without clocks, this can be done. For example, the local times at which lunar eclipses take place can be measured in various places and compared, and the differences in longitude between those places can be found. This isn't useful for navigation (because you don't know anything useful until you compare those measurements), but it is useful for improving the accuracy of maps. The motion of the moon can be used beyond the simple timing of eclipses, but this take pre-calculation of the motion of the moon in its orbit (and developed into an important 18th century technology for navigation, with

On Medieval European maps and/or tables of latitude and longitude of various cities, the errors are usually quite large. Errors in longitude are often about 10 degrees (about 800km error east-to-west) and latitude 1 degree (about 100km error north-south). The best measurements could be much better than these, but were not systematically used. It appears that good enough was considered good enough, and that there was no need for high accuracy [1].

Improvement in measuring instruments (such as sextants) and accurate lunar tables (e.g., Mayer's mid-18th century tables based on Euler's formulae) brought improved accuracy, useful for navigation as well as for mapping. With repeated measurements to reduce measurement errors by averaging, the east-west position could be determined with an error of about 20km. In practice, this was time consuming (to obtain the repeated measurements), and lower accuracy was usually accepted (errors of perhaps 100km). Latitude, on the other hand, could be reliably measured to within a few km (say, 2-3km). Also in the 18th century, reliable and accurate clocks, sufficiently robust for use at sea and sufficiently accurate to determine east-west position to within 20-30km, were developed (Harrison's marine chronometer).

After this, the instruments continued to improve. As a result of this, 19th century maps had become quite accurate. In addition, triangulation to find the distance to a point combined with accurate direction measurements (e.g., with a compass) lets one find the position of points relative to nearby reference points, and can be used for mapping. This is especially useful for mapping the interiors of continents, and also contributed a lot to the accuracy of 19th century maps.

The impact of improved position measurements methods can be seen in the series of world maps shown in https://www.reddit.com/r/MapPorn/comments/932wrc/the_history_of_accuracy_in_world_maps_oc/ (and the greater accuracy of latitude measurements compared to longitude measurements can be seen).

References:

[1] John Kirtland Wright, (1923), "Notes on the Knowledge of Latitudes and Longitudes in the Middle Ages", Isis 5(1), 75-98. http://www.jstor.org/stable/223599