I think "to Google" as a verb for "to search on Google" is OK, but only informally. I use it myself. However, it has become synonymous with "to search on the Internet, regardless of search engine used" which plays into the hands of those evil corporate types.

It has, of course, an friend in "to hoover."

Right on cue, Slashdot reports that "Google Sends Legal Threats to Media Organizations" over the use of its name as a verb for internet searces. See here.

...and in case you didn't scroll all the way down, here for some wonderful derivations from the Japanese verb 'guguru'.

That story suggests that 'to Google' becoming a generic verb doesn't necessarily benefit them, though, because they lose their exclusivity.

To be more specific, potentially they could lose their trademark (at least in the US) if it becomes an ordinary word ("google" isn't an English word yet, although "googol" is), as once a word has become a generic term, it becomes impossible to enforce trademark rights on it.