There's probably a more technical way of doing this, but:
Go to the main google page.
Click once on the search line - the full list of previous searches will appear.
Hold down the delete key until they're all gone.
You might have to do the same for both browsers.
Hope that helps,
AV8.