Looking at the responses to this question, it seems that a mobile service provider can't automatically detect whether or not a phone user is tethering their phone or not. Though they can infer it by the type of activity a user does.
However, my service providor charges extra for both USB and WiFi tethering. They can provide accurate usage statistics and charge by the data packet, so they must have some deliberately set up way of monitoring this. I believe the most likely way of doing this is they likely have some kind of software built into my installation of Android that reports whether or not I'm tethering.
So, does that mean if I root my device, and then presumeably that software is gone, they won't be able to tell anymore?
I'm weighing the risks and rewards of rooting my phone, and whether or not I could bypass their nickel-and-diming by charging extra for tethering would be a deciding factor.
SSH Tunnel
to route all your traffic through it. they can't detect anything from your encrypted tunnel.