Here are the instructions from the Electronic Frontier Foundation on how to clear you browsing history. If you use multiple Google accounts, you'll want to delete browsing history for all of them. If you don't take these steps, all of your browsing history will be combined with and shared across all the other Google services you use. If you're not sure why this might be a concern, see this EFF post and this Slate article ... or search on it!
You might also consider trying out an alternative default search engine. Many people (me included) are now using DuckDuckGo. This search engine does not collect user data and emphasizes privacy. It's quite capable, although I do notice differences in terms of rankings and results compared to Google. That's not a bad thing, it's just different.
If you're using Chrome, it's easy to change your default engine. Look under 'Preferences' > 'Manage Search Engines.' It's relatively easy with Firefox, too. You'll find the option to manage search engines by choosing the dropdown arrow located in the browser's built-in search box. With Safari, it's a bit more complicated because the browser only offers Google, Bing, and Yahoo as default search engines. You can make DuckDuckGo your default, though, if you install the free Glims add-on.