1. Go to https://www.google.com/history and sign into your Google account.
2. I recommend going through your search and Web History to see if there's anything in there that you might want to keep before you delete everything. I had a web history stretching back to 2006 and it was quite interesting seeing the kind of videos I was watching at that time as well as the searches I made. It also gives you a chance to save and keep links that you'd either forgotten about or overlooked. Such as, ahem, this little gem:
3. Once you're happy there's nothing you want saved, simply click Remove all Web History. Click OK to confirm, and you're done. For some reason, I found that I had to repeat this step as it didn't remove anything the first time. Note that deleting everything also automatically Pauses your Web History, which prevents Google sharing some of your data across services, until you choose to reactivate it.
The Electronic Frontier Foundation stresses that disabling your Web History in your Google account will not prevent Google from gathering and storing this information and using it for internal purposes.
It also does not change the fact that any information gathered and stored by Google could be sought by law enforcement. With Web History enabled, Google will keep these records indefinitely; with it disabled, they will be partially anonymized after 18 months, and certain kinds of uses, including sending you customized search results, will be prevented.
Although Google have done a good job of publicizing the privacy changes, I recommend reading this impartial post for an excellent lowdown on exactly what these changes mean for you the user.
Finally, if you're concerned about Google sharing your data across services after March 1st, don't forget to check out our simple tips about How to stop Google tracking you across services.