The current legislation in Australia requires service provides to retain metadata for two years. In parallel, everything you type into the search bar on Google is retained with your IP address and other relevant details - even if you have never registered a Google account. Therefore, your Internet browsing activity can be reconstructed and linked back to you by correlating the different datasets with each other.
To avoid these data correlation issues, you should switch to a search engine that does not retain any logs of your search queries. Because search query logs do not exist, there is nothing to correlate with the metadata at your Internet service provider.
Keep in mind that these search engines only provide a basic level of privacy. For full anonymity on the Internet, you should look into other tools such as the Tor browser.
StartPage is a search engine that providies similar quality results as Google. The trick is that the engine proxies your search queries to Google. However StarPage does not retain any metadata of you. From Google's perspective it appears that each search query is coming from StartPage. Unless you are searching for something very personal on StartPage, it makes hard (but not impossible) to reveal your identity.
DuckDuckGo, on the other hand, does not forward your search queries to anywhere. They index the web on their own, so the search results may differ compared to Google or Bing.
Photo courtesy of Rainer Hungershausen