Verizon has rebuffed and criticized Google in the past, being the only major operator to publicly denounce Google's Android initiative (a "software stack" they've developed for mobile phones that is based on Java and and includes such features as an integrated browser and media support) and their open-spectrum plan - but they've let bygones be bygones and are working on creating a mutually-beneficial relationship.
The deal, which is currently still in the works, would make Google's search engine the default search option on Verizon's handsets, and Google will in turn give Verizon a share of ad revenues. The main problem at this juncture is Verizon's aversion to Google's desire to save info from the cell phone searches; a stance I'd venture to guess a great deal of consumers can agree with.
According to the report from Yahoo Finance, the deal could be finalized within a couple weeks, so if you're going to be upgrading your Verizon cell soon, be prepared to see Google right on your home screen.
Discuss Verizon's partnership with Google on EVDOforums