Also, how were maps made/oriented before compasses/lodestones were in widespread use?
This comes more from my work making me kind of a cartography nerd, so I apologize that some of this is more logical than historical, but your question is best answered that way.
The acceptance of East and West is pretty universal across cartographical systems, even before the use of any compass based system, because of the rising and setting of the sun. The names "east" and "west" take their names from dawn and evening (German), and the sun is one of the oldest and most constant ways of tracking position we have. The placement of North and South would have largely been relative for map makers before compasses, but still was largely consistent across map schemes regionally.
This is a long way of saying that even though we weren't calling them North, South, East, and West, most sun based systems of cartography would have lead to most groups being able to agree on the cardinal directions.
This does exclude, however, groups that lived on island or relied heavily on coastal living (or mountains, or lakes, etc.), where you would have likely seen a more object relative cartographical system. Once a group began traveling more than about 50 miles though they likely would have resorted to a "dawn-ward" "dusk-ward" system, and would have then recognized the directions perpendicular to those.
I'm pulling a lot of this out of my own databanks, but I'm sure a rundown would be available in "The History of Cartography", specifically the first three chapters of volume one. It's published by Chicago University Press for interested parties.
hi! more responses are welcome, meanwhile you may be interested in these posts
Is it an coincidence that the Pyramid of Cheops lines up so well with the Google Maps window?
How did early navigators develop a system for figuring out North, East, South, West?
... and this FAQ section, which has subsections about why North is typically "up", examples of old maps, and the history of cartography