If I root my phone, can my service providor tell if I am using my phone for USB tethering or as a WiFi hotspot? 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.
Technically they can inspect the HTTP Headers and look at the User-Agent field to determine browser and OS; but imagine the millions and millions of HTTP requests for web pages and applications in a given day.

They can do trends, and data mining techniques to find out - but is it worth all that effort for them just to track down someone using a few more MB of bandwidth? Probably not.