Oxford English Dictionary, the most comprehensive dictionary of the English language, has added "google" to its latest revision. You can find the entry by searching for "google" in this page. The verb "google" has been used in the recent years with the meaning "search (something) on the web", even though you use other search engine than Google. Google comes from the word googol, which means 10100, and was coined by Milton Sirotta, nephew of American mathematician Edward Kasner. Larry Page and Sergey Brin didn't know the proper spelling of the word, so they've used Google to illustrate the huge quantity of information available, but not yet searchable.
Probably the first reference to Google was a cartoon called "Barney Google and Snuffy Smith" that was first published in 1919 by Billy DeBeck.
Update: Google is also listed in the latest edition of the Merriam-Webster Dictionary. The Age speculates that Google will have a hard time defending its trademark. "If you can bring evidence to show that such a word has general currency, then anyone can use it," says Susan Butle, an Australian publisher.