If you use a program like Ccleaner and it is set to 35 passes it will delete history completely, but in many cases it is also possible to recover it if it has been simply deleted with a program such as Pandora.
CCleaner, it deletes your cookies and history:
http://www.download.com/CCleaner/3000-2144_4-10315544.html
Click on the Cleaner Tab on the left and under Windows tick all boxes in Internet Explorer. If you save your username/passwords untick 'Autocomplete Form History' and under System tick all boxes except the last 2, and leave Advanced all unticked.
Then click on the Applications tab and tick all apart from Saved form information if you use Firefox and save your username/passwords
Click on Options then Settings and under Secure Deletion mark the Secure file deletion (slower) and use the drop down to select Guttman (35 passes)
Please note that some files are 'locked' but will be removed on shutdown.
Pandora Recovery 2.0.1
A powerful free tool that provides its users an effective way to attempt recovery of permanently deleted files. It successfully handles archived, hidden, encrypted and compressed files and recovers Alternate Data Streams (ADS). It also has ability to scan drive clusters, picking up files whose MFT record has been reused by OS, damaged or recreated (it can restore files on formatted drives).
http://www.download.com/Pandora-Recovery/3000-2094_4-10694796.html?tag=mncol&cdlPid=10865321