This isn't just a matter of advertising. Your search history is an incredibly personal and detailed profile of who you are, and governments have a history of trying to use that sort of information for $badThings. See: US DOJ request for search engine histories in 2005. There's a reason why librarians fought so hard to keep your book checkouts private when the Patriot Act passed. Search histories have a potential for abuse and their privacy should be an issue.