If you only cleared the history from within your Web browser, it can be easily recovered. History is also stored in the registry and .dat files which can be read with special software. These files keep logs of everything you do. CCleaner will delete all traces of your online activity including the index.dat files making a restore nearly impossible - just make sure to enable the "secure" delete option. CCleaner is free and highly recommended.
