1. Go to http://www.google.com/history
2. Sign in with your Google ID and Password.
3. On left hand side click Remove items.
4. Click Clear entire Web History (Which will clean all the history that is recorded in there)
5. Go back to Remove items and then click Remove. This will stop Google Web History from being recorded in the future.