There is a very long article today in the WallStreetJournal called Coming Soon to Cellphone Screens — More Ads Than Ever.
Several US Mobile phone operators seem to test how they will be deploying ads on your mobile phone. Yahoo! seems to have a deal already that is placing it on the go2 directory where you find e.g. the nearest restaurant on your phone. In the new search results Yahoo! ads will be placed. Carriers using go2 search and having the links are Verizon Wireless, Sprint and Cingular Wireless.