Multiple different detection methods:
-Your phone queries the network to see if tethering is permitted, or it explicitly tells the network it's tethering.
-TTL value on packets are an unexpected value. If many of your packets have a TTL of say 30, but they suddenly see an influx of packets with a TTL of 29, that's a sign
-Examining MAC addresses. Similar to above, if they normally get packets with a MAC of XYZ but then get a bunch of ABC, sign of tethering.
-Fingerprinting of the network stack. By examining characteristics of network settings they can guess what OS is being ran
-Examining data and URLs. Was a desktop webpage requested? Did the user agent match to a desktop OS? etc.
Not everything is foolproof and guaranteed-false positives would be easy to happen. But it's not very hard to detect if the person is lazy. End to end encryption and running everything through a VPN tunnel can help mask many of the detection methods.