Nara Schoenberg, "Don't Go Into Date Blind; Singles Googling Before Canoodling," Chicago Tribune, April 2, 2001
Amy Gilligan, "Googling is newest date thing," Telegraph-Herald, January 14, 2001
Here's a citation illustrating the more general sense of the verb:
"Novelist Dave Eggers to speak in Denver," The Denver Post, September 10, 2000
Using google to scope out a new boyfriend or girlfriend which has also been called Google dating and interpersonal espionage took off after a lengthy article on the practice appeared in the January 15, 2001 issue of the New York Observer. However, the honor of the first print citation goes to the Telegraph-Herald, which published a story just the day before (see the earliest citation, above).
Note, too, some people claim you can only use the verb google to refer to a Google search. That makes sense, but how people use language often isn't sensible (how dull that would be!). Google is being used in a more general way (by jordan). For example, one person told me that their daughter said she was "googling for her other sock." And here's an example citation (one of dozens I could provide) that shows the use of googling as a synonym for "searching the Web":
Once, the prospective girlfriend devoted considerable time to the predate ritual, switching dresses, reapplying lipstick, declumping lashes, and, perhaps, calling the friend of a friend of a friend who might remember the date's name.
These days, date-readiness requires roughly the same amount of time, during which the investigative dater, suited up in her regulation black shift and clumpless mascara, gives the boyfriend-applicant a once-over. This process reflects none of the cuddliness implicit in the term "Googling."
With the assistance of her high-speed Internet connection, she scans and fact-checks her suitor's resume. Her short, buffed nails pull up his credit history, mortgage schedule, publications record, professional reprimands, genealogy and horoscope.
Leah Eskin, "Getting to know ALL about you," The Chicago Tribune, February 9, 2003