[AT&T, Rogers, Bell, Telus Samsung Galaxy S III] bitbang3r:
If your PC/Mac-originated traffic is being regenerated by an Android-hosted app like EasyTether (so it officially originated with the Android app, as opposed to having been routed by the wifi driver and kernel iptables), it would be extraordinarily difficult for the carrier to figure out its true nature without deep packet inspection. If you tunnel it over an IPsec VPN using PPTP or L2TP, it would be damn near impossible for them to establish tethering with enough certainty to ever prevail in court unless you were literally tethering daily as your primary means of getting online, as opposed to tethering once in a while when you lacked better access options (airport, beach, car, etc).

Traffic analysis can certainly SUGGEST tethering and get you flagged for an automatic nastygram informing you that it's going to be added to your plan unless you complain, but if you're using an ADB-type tethering method and tunneling, you could tell your carrier to go f**k themselves and prove it with a very high degree of confidence. If you have a data plan that's tiered, I can't fathom them investing the resources to prove that you're tethering once in a while. In the AT&T context, somebody who's tethering on a regular basis with a tiered data plan is going to go over 5 gigs and end up paying the same amount he'd have paid to openly tether anyway, and somebody who's only tethering occasionally & not exceeding 3 gigs/month wouldn't be worth the effort to track down.

Add the fact that most carriers (in the US, at least) either rate-limit your traffic after 5 gigs (or less), or (in the case of Sprint) will actively dump you as a customer if you routinely exceed 5 gigs month after month after month (as if anyone could actually exceed 5 gigs over their glacial, dysfunctional network anyway), and the business case for aggressive tethering enforcement that goes beyond looking for routing signatures in the datagram becomes almost nonexistent.

Now, if you have an unlimited data plan that they're itching to terminate and force you into a tiered plan, they might try a little harder... but if their payback potential is an extra $10/month (because you have a tiered plan and you're already paying them $40/month for 3 gigs plus an extra gig, instead of paying $50/month for 5 gigs you might not fully use), they aren't going to bother, especially if you push back. Remember, there are data privacy laws, and most of the things they'd have to do to prove tethering if you're actively obfuscating and tunneling your traffic are borderline greyhat hacking. A big corporation isn't going to risk getting smacked down by federal regulators over pocket change. They're going to shake down the easy targets, and move along.

Insofar as deep packet inspection goes, remember... it might be easy to gather enough evidence for them to auto-send a nastygram and auto-subscription notice, but it's HARD to gather enough evidence for them to risk pursuing a case against someone who's actively fighting back. Five years ago, it might have been easy to notice tethering from a J2ME, Blackberry, or PalmOS smartphone by looking for implausible traffic. Nowadays, there's very little traffic that couldn't plausibly be generated directly by an Android phone. RDP and VNC? Check. IPsec VPN? Check. SQL client? Check. SSH? Check. Bittorrent? Check. (Suicidal and insane, but plausible). Desktop browser identifiers? Nope. Android's own browser can spoof desktop browsers with casual ease (about:debug, then menu->Settings).

The way to win against your carrier is to make victory too expensive for them to bother with. They're looking for easy ways to boost revenue, not embarking on a moral crusade to stamp out tethering. Make victory more expensive for them than stalemate, and they'll leave you alone.