rawprawn's link and the use of Ccleaner in default mode clears Google etc searches, but not, for some reason AVG (if you have it's toolbar) I have found a long winded answer to this: I went to Cleaner- options- advanced -include. Then added: C:Documents and settings/(user name)/application data/AVG Toolbar/combosearch.acs - replace username with your own user account name - seems to work! I could not get AVG to clear searches in its toolbar any other way.Do try CCleaner - it is very easy to use.
I think you were specifically refering to search, rather than browsing history. What toolbars do you have? In google,click the little down sign at the left of the g search panel in the toolbar,click view history, then delete all. For AVG see my 17.30 posting.