Water. Not only drinking water, but water on their skin, like a lake they went in or something.

I have heard it said that vegatables tested in the past compared to now were found to have 3 times more magnesium than in modern times. If true, that would explain a lot. Basically, it would mean even if you didn't change your eating patterns, if foods had the same amount of magnesium as in the past, your magnesium intake would be tripled. However, I am not sure how well substantiated those numbers are.

On the flip side, it could be that certain modern living practices or toxin loads are increasing current needs for magnesium.

Or there was some source of magnesium in the past that we just aren't thinking of. But frankly, even counting bone broths and other supposedly high in magnesium foods, basically if you aren't eating spinach and salmon every day, or supplementing, you would be hard pressed to regularly reach standard RDAs for magnesium. (and I might add that the magnesium RDA does seem to be important to meet for many people)

maybe from water?

The soil was much richer and less depleted back than, so they got a lot of there minerals either from the natural soil or the water. Sadly we don't have high quality soil or water so supplementation it is.

Green leafies are a great source.

http://nutritiondata.self.com/facts/vegetables-and-vegetable-products/2627/2