its the software on your phone. if you load a custom rom it usually has tethering for free. at that point the only way they know is your data usage and thats arguable.
A device will build ARP tables, yes, but only for the purpose of remembering which MAC is assigned to which IP on its local network.
Once the packet gets routed out by the phone over the carrier network, the MAC address is changed in the header to the MAC of the phone radio.
Everything on the phones local network can't be seen by the next hop, because it doesn't need to be. If it did an ARP lookup, it wouldn't be able to see the laptop you're tethering.
i use foxfi for my internet at home because our POS cable company wont run a line down my drive way. the orange cable is literately running down the pole at the end of my drive way..... so luckily i have pretty good 4G service from verizon so i abuse the fuck out of it. i'm right under 200gig and about 3/4 of the way through the month. my normal month is about 150 gig. i have one of the old unlimited data plans so i buy phones and never change my plan.
I think they know what user-agent your'e using. As in the browser is mean't for a pc. There are apps for chrome that makes the browser "pretend" it's a phone.
I use tmobile to tether and that trick lets me use unlimited data when browsing. I haven't done it in a while, though. There's a chance they may have found a way to work around that.
Apn on the net.. They may use one or a combo of all of the above.. However if you run through a Vpn with the tether then they can detect you so they will monitor aggregate bandwidth according to time slots. They will see the difference between a desktop and a little mobile phone