Wate from natural sources (those not polluted by civillisation, relatively rare these days) is relatively pure, pure enough so that it doesn't require any purification before it can be drank. And don't forget that our immunological system is a pretty robust thing, able to deal with most bacterias and pathogens.
So the short answer is - in most cases they didn't have to purify water, as long as they carefully selected sources.
OTOH, have you seen a dog drinking from the puddle? Dogs do it all the time and they don't die. Do you think their bioogy is that different from ours?
Not that I am proposing you to drink from the next puddle you will see to check it, that's just a gedanken experiment
Finally, natives usually know of tricks that we have long forgotten - like adding some kinds of soil/sand/rocks or plants to water in order to change its taste and biological purity.