By two ways: either they find relevant inscription (typically on tombstones) at the site, for example signifying the location of a death of a soldier.

But the easiest way was by using an itinerarium, the roman equivalent of our maps - though these were more of a list of places with distances between them noted in roman miles (approx 1430 meters) along roads - the traveller could know the distance he passed thanks to the milestones erected along the cursus publicus, the system of viae (roads). There are surviving examples - notably Tabula Peutingeriana - which do resemble a map, showing some landscape features and waypoints (like rivers, crossings, forts etc). Despite appearances it doesn't qualify as a map, but rather as a chart or diagram. The itineraries themselves were copies of the master itinerary, typically compiled per the emperor's orders.