Jacques Mattheij wrote a blog post named Google Web/Search History Disable Does Absolutely Nothing. Basically claiming that when you hit that delete button, Google just hides it from your Google Web History page but does nothing more.
Of course, this upset Google's Matt Cutts, who said he was wrong.
Matt posted on Hacker News:
Just a quick point. The article says "there is no guarantee whatsoever that google does anything except for changing what they display to you."
If you're on the page at https://history.google.com/history/ and click on the gear and then "Help" the page about deleting search history is at https://support.google.com/accounts/answer/465 and it says
"What happens to your history when it's deleted
When you delete items from your Web History, they are no longer associated with your Google Account. However, Google may store searches in a separate logs system to prevent spam and abuse and to improve our services."
The article claims that there's no guarantee that Google does anything other than change the display. Google actually does quite a bit of work to disassociate items from your Google account if/when you delete them.
He then explains why Google does keep the search results for 18 months, for spam reasons. Matt said, "an easy example of preventing spam would be to detect and stop people trying to spam Google Suggest, which is based on queries that users do."
I am sure many of you will enjoy that last quote, because clearly there is a lot of Google Suggest spam attempts that Google watches over.
Either way, technically, there are likely ways to associate your searches back to you even if you delete them. Like in the AOL example from 2006. But Google does do things to disassociate the queries to your Google account.
Forum discussion at Hacker News.