This line in their Privacy Policy makes a bit hesitant.

When you use Google Web Accelerator, Google servers receive and log your page requests.

Although I'm pretty sure it is only cashed for similar purposes as browser history on computers.

Well... they actually do it because they store a temporary copy of the entire page on their server. That's how they speed things up. They cache pages on their servers so that if multiple people request the same page, they can just use the cached version. If a page changes periodically, they can send you just the difference between the copy you have, and the new copy as well (reducing speed). They also utilize compression. All those things require that they receive and log your requests.

The question is whether they associate the request with some identifier on your machine allowing your requests to be tracked. They already do this somewhat using the Google toolbar. The toolbar actually sends the search phrase to Google, along with an identifier. Now then, they say that the identifier is not associated with you... so someone couldn't say... tell me all of Sandi's searches. But they might be able to ask for x837fkdl4543's searches.