Yes & No (unless use TOR). To ask the question is to answer...they will do whatever they can get away with. Haven't you heard of the Snowden revelations?
https://tor.stackexchange.com/questions/8/how-does-tor-route...
Verizon has been adding headers for tracking for some time (probably via Blue Coat ProxySG forward proxy or similar technology) https://www.verizonwireless.com/support/unique-identifier-he...