Tethering can be seen easily
When you tether a device, it adds a unique identifier onto the data packet. That allows your device to route any return data back to that device. A monitoring device on the carrier's network can classify two different identifiers on your device. Bingo, you are nabbed That is how NAT works.
Pompano Beach, FL
Fortunately... The unique ID are TCP/UDP port numbers.. The same port numbers used by cell phone internet accessing. The NAT program keeps track of which port numbers are used by which program and/or NAt'd device. The NAT also makes up fake port numbers and remaps those port numbers in packets flowing from/to networked devices.
Thus if done right(which linux/andriod usually does).. there will be no difference between cell phone IP traffic and NAT'd traffic..
P.S Most teleco sniffers look at the browser id string in the http get request as a tethering detection. But those ID strings can also be faked..