Just click on the Search History link, click on Remove Items from the left, click "clear entire search history," and click "clear history" on the following screen. It will then let you know your search history is empty.

Hope this helps,

P.S. This is actually a beta function Google is testing. You can opt out by selecting "Pause" from the left-hand side instead of "delete items."