How does the carrier know that the traffic is being proxied for another device, and not e.g. requested from the phone's web browser or another app?

Does the phone add a proxy header? Can it be configured to not add the header?

There might be multiple methods and heuristics, but one way that I have encountered was based on packet TTL.

Android and Linux use 64 by default - the block could be circumvented by setting the laptop to use 65 TTL.

Mostly by looking at packets TTL. It gets decreased by 1 by the hotspot’s NAT so if the value is something like 63 or 127 (instead of 64 or 128 which are the defaults for most platforms) then it’s almost certain the packet originated from a device behind the phone and not from the phone itself.