Google promoted Adwords ads as "Ads by Google" earlier. Now they are using "Adchioces" instead of "Ads by Google" Check this out for more info: http://adsense.blogspot.com/2011/03/new-in-ads-notice-label-and-icon.html
Not only the Google to have AdChoices mark on Ads, there are many other networks, companies, agencies using the "AdChoices" mark. AdChoices is a Independent online Advertising regulatory program which is no way affiliated with Google Adsense/Google/Google Adwords. Pleae check: http://www.mohith.net/2011/06/what-is-google-ad-choices-i-icon-in.html
Actually, i came to know that at first itself, when i am surfing the web (other ads also showing the "mark" so i doubted and searched on google). And finally i found this http://www.aboutads.info (Self-Regulatory Program for Online Behavioral Advertising)