For directions there's a million tricks to orientate yourself in the wild that they would certainly have been aware of. For a relevant one in contemporary times, the claim that moss only grows on the e.g. north side of trees is mostly true. A more accurate description would be that moss likes to avoid the sun and so tends grows to grow on the side of trees least exposed to the sun, which in the northern hemisphere tends to be the north side. It's going to vary by location/environment/etc but they would have known these things (and countless others) and so the environment itself would have been a living compass.
Apparently there's one tribe that doesn't even have a term for left/right/etc but instead uses solely cardinal directions. No idea if this is another bbc style claim or actually true, but it's at least completely viable.
It was not like today, when "rest of the groups" sits at home all day, and expects everything on silver platter!