Seriously, this is the best advice. It has been used for literally hundreds of years as people changed their name and moved to a new town to escape a reputation or community memory where they lived.
But if you want to be more deliberate about it, then the question you have to ask are "Who would be looking for you on the Internet and not like what they found?"
That runs the gamut from old classmates to people you're dating to current or future employers to federal agents.
Stay off Facebook and legally change your name, that will protect you from old classmates. If you're running away from bad reviews on dating sites you may need to change your name, move, and change your haircut and appearance. If you are worried about employers you'll probably need to change your social security or taxpayer ID. That gets into the realm of felony territory so you're going to want to be thoughtful about that. Without it though the IRS can connect all the dots and there are various ways background checks can do the same thing.
The alternative might be to try fuzzing, basically create a bunch of accounts with your name and be different people on each of them. That has the down side of obviousness in terms of obfuscation.