The EFF has an online article showing how to clear and pause your web search history in a few simple steps.
However, this didn't work for me; when I tried to direct my browser to https://google.com/history, as instructed, I was automatically redirected to my iGoogle page.
What I did instead: I clicked the gear symbol in the upper right corner and selected "Web History". That had the same effect.
Hat tip to Beelzebjörn (in Swedish).