How Do I clear Google Toolbar Search History?

Click on Google logo on the toolbar and from the drop down menu Select the "Clear Search History" option.

If you want to completely disable your Toolbar's search history:-
Click the "Options" button on your Toolbar and un-check the box next to "Drop-down search history."

If it's version 4:-
During searching an item when your drop-down search history appears, simply click the "Clear History" link.

If you want to tweak through the registry:-

Start>Run>Regedit>OK

Now navigate to the following location:-
[HKEY_CURRENT_USER\Software\Google\NavClient\1.1\History]

Select the History subkey and delete it.Close the registry editor and restart the system.