I just did it and it’s simple.
Sign in, go to google.com/history, and choose “Remove All Web History”. This also revokes your consent to have your search history recorded going forward.
Needless to say, protecting your privacy should be the default among web-based corporations and organizations, and you shouldn’t have to opt out of anything at all. But even for the great “Don’t Be Evils” out there, the pressure from shareholders to turn you into a product is strong, and your concerns about keeping your shit to yourself are pretty much immaterial unless they affect the bottom line. So opt out, stick it to the man, fuck the police, etc.