Also, I forget to mention, you can use the private search engines like DuckDuckGo or StartPage in the browser to have completely private search history. StartPage even has it's own 'VPN' type service, where you can click on a link and it will browse to the page through StartPage's own proxy so you can browse totally anonymously.