As a noun, always capitalize it. It's a trademark and a proper noun. You are using it to mean the one search engine (or company) only.
As a verb, it is generally still capitalized, although you will also see it without.
I stress that this is only my (unsubstantiated) opinion, but I think capitalization of such words is often a question of age and acceptance. In the UK, we "hoover" the carpets without a second thought or a capital letter and we "bowdlerize" to our hearts' content. We make herculean efforts not to spill our irish whiskey and so on.
Perhaps we would only feel happy lowercasing it if we were to use "googling" in the sense of "searching with any type of search engine".
Strangely, however, in the US you generally use a Kleenex with a capital letter no matter what brand of paper tissue you are actually holding. I nevertheless don't think there's a significant distinction between usage either side of the Pond.
Chicago Manual of Style, 14th Ed. 7.49 seems to have it about right:
"Nouns, adjectives and verbs derived from personal, national or geographical names are often lowercased when used with a specialized meaning. According to some authorities, however, certain of these ought to be capitalized. Authors and editors must decide for themselves, but whatever choice is made should be followed consistently throughout a work."
Reply from Phil White (Munich - Germany)