I'm not sure how PDAnet and the other jailbreak solutions work exactly so i will not talk about them. However, if you look at how the built in tethering capability of the iPhone works, it is quite possible for them to know if you are tethering.
When you tether, over bluetooth or USB, that interface gets a private IP (my usb interface usually gets 192.168.20.1), and the computer interface also gets a private IP (mine gets 192.168.20.2). Basic networking will tell you, if you have a private IP and are getting on the internet, you are going through a router running NAT. Since the iPhone's 3G (or edge) signal is what you are connecting to, your phone is in essence acting as a router running NAT. A quick little diagram.
Computer (192.168.20.2) >> (192.168.20.1) - iPhone - (3G IP addr) >> Internet.
Since the iPhone connects two different networks together, it is acting as a router, and when packets pass through a router their TTL is decremented. AT&T could theoretically see when you are tethering by looking at the TTL of each data packet being sent, if they see a TTL one less than what it normally is, it is an indication that your phone is routing packets, therefore you are tethering.