In an draconian move, AT&T begun sending out a stern letter to tetherers requiring that they stop tethering or automatically be added to a $20/month DataPro plan. Please note; DataPro is also capped at 4 GB, so presumably any customer on the grandfathered unlimited data plans from older iPhone plans would also lose that facility.
An app called MyWi allows you to tether your iPhone or iPhone 2 without AT&T's explicit permission. As per AT&T contract using MyWi and other apps is, in short, forbidden in the carrier contract.
AT&T's mailshot explaining that its "records show that you use [tethering] but are not subscribed to our tethering plan." iOS, of course, will disable the built-in tethering facility if you do not have an appropriate carrier plan.
So how does AT&T know? The company isn't telling, of course, because that would immediately set people off figuring out ways around it. This reddit thread has some good technical speculation on what might be going on. It could also be something, such as checking the ID string that all web browsers send as part of a request. If a given account doesn't have tethering, but it has lots of browsing activity from, say, Firefox or the OS X version of Safari, it's pretty much guaranteed they're using something like MyWi.
This simple check could easily be bypassed by using a VPN on the tethered device, stopping AT&T from seeing inside the traffic.
Here's AT&T's full letter: