Those saying that carriers have a way to determine whether or not you are tethering are most likely correct. However, to determine that, you would have to examine individual packets. Unless the situation got really bad, this is likely not a route that any carrier would bother going down.
In this case with AT&T, there is a crucial bit of information that has been left out of this thread (and most news articles covering this story). The forum on which this was originally reported has updated their post to note that many people have received this notice from AT&T, even if they haven't tethered (heck, many of them haven't even jailbroken their devices). What everyone
did have in common, however, is that they all used very high levels of data in a month's time. Think 15 GB+.
Again, not all of these people tethered. Some of them ran up that much data usage legitimately through various streaming apps, such as Netflix and Pandora.
So what does this mean? That means that while AT&T probably has the capability to determine who is tethering (as I mentioned before), that's not what they're doing. They're simply sending out mass texts and emails to those who break a certain usage threshold. All AT&T is trying to do is get some people to admit to tethering, and hopefully get frightened into purchasing the tethering plan.
Numerous people have already called AT&T and disputed their accusations. People have told them that they don't tether, and that they used that much data through streaming applications. And regardless of whether or not these customers actually tethered, AT&T representatives have apologized for the mistake, and have changed their accounts so that they will not auto-enroll for the tethering plan.
At this point, this is nothing but AT&T bluffing. Call their bluff.
(One final note... for those of you using the term "illegal" with tethering... oh man, you guys crack me up. :laugh