Amazing. How do they tell whether you're tethering, though? If you're using your own smartphone, I mean.

There's various ways:

Some rely on the device itself to enforce it, but that's obviously fragile if you can bring your own device.

Some check the TTL of your packets when they enter the carrier's network, because tethering is at least one more hop and so even if your computer's OS and phone's OS agree on what TTL starts at, the TTL will still be different than expected for your device's platform. Obviously this can still be mitigated by adjusting your TTL, but outside of software that'll handle this for them, that's already beyond a lot of customers.

Some even take the route of only checking HTTP traffic, and detecting tethering based on User-Agent, but I think a lot have abandoned that because it doesn't catch other protocols, and is easily bypassed even on HTTP.

They don't, but on-phone software (stock iOS, as a prominent example) enforces the policy.

I was furious when I bought a Nexus 7 (first version) and found out that tethering wasn't available on the device (although there was no obvious reason it shouldn't be and rooting the device would have allowed me to enable it). Running into this on stock devices seems absurd.