Yep! I take it you mean the Google Toolbar (and not the Deskbar or Desktop Search). Click around that area (there should be a button near the text box) and options should appear. One of them should let you delete all of them. Also, try and go into your Google Toolbar's options and look around for an option of search history (it's a check box, just uncheck it).
Good luck, Sid