They didn't (and don't) just dig randomly. You're more likely to find water at a lower spot on the terrain than a higher spot. The type and amount of growth is a tipoff, too. Plants like blackberries love water and are a good indicator of an available source, for example.