As you may have read lately, Verizon have implemented a system that adds an HTTP header item in all web communication that originates from mobile phones on their network. Each phone/user get their own unique ID, which is transmitted to every website being visited (except if SSL is used), no matter if you have privacy/anonymous surfing turned on in the browser. The id stays with the phone, no matter if you connect in a different city or if you get a different IP address.
This series of about 50 characters is called Unique Identifying Header (UIDH) and is a key part of Verizon’s internet advertising program. And even if you as a user would opt-out of the targeted ad on Verizon’s website, any web server or ad network out there can build their own database of users based on the UIDH.
What has not been as widely mentioned is that AT&T is doing exactly the same. They add a header item called X-ACR (which is 350 characters long) to all outgoing communication. And this one you can not opt-out of, as AT&T have not even confirmed that they perform the tracking. According to this article, T-Mobile is also testing something similar.
You can test it yourself at http://lessonslearned.org/sniff. Make sure you are not connected using wifi, then simply open that link from your smart phone and you will see what headers you are transmitting. I tested it myself, using my AT&T phone, and verified that the X-ACR header is there.