The latest edition of Merriam-Webster's Collegiate Dictionary features about 100 new words, and one of them is "google":
"Google is definitely a verb," said Dan Reynolds, a 35-year-old salesman at YES Computers in Northampton. "Google has become like a secondary brain for a lot of people. If you want quick info on something, that's what you do. You google it."
Respectful of the trademark, Merriam-Webster lowercases the entry but maintains the capitalization while explaining that the verb means "to use the Google search engine" to retrieve online information.