If you put a straight stick in the ground, the shortest shadow is due north (when north of the Tropic of Cancer). Drawing the perpendicular is easy. You can also use the sunrise and sunset shadows and bisect that angle to get the north-south line any time of the year.
I have heard that they also used the north star at the time, Thuban, to mark north and that estimates on the age of structures could be made based on deviation fron true north caused by orbital precession.
I hear tell that the Southern Hemisphere lagged behind the Northern Hemisphere due to them not having a Star that the Southern axis pointed to.