The instructions are simple. When logged in to your Google account, go to http://www.google.com/history and click the “remove all history” button, confirming it on the next page. That’s it. That will remove your search history and keep your history from being recorded in the future. It is also important that you do this for all of your Google accounts and for some of us, that might quite a task.