Not sure how they can tell. I and several others I know have been doing it for quite awhile and on several different kinds of handsets with no problems to speak of.
First, high bandwidth use. Tetherers tend to use more bandwidth. That's the heads-up. Second, deep packet inspection. For example, if an HTTP request from an Android phone has a user agent string of "Mozilla/5.0 (Windows; U; MSIE 9.0; WIndows NT 9.0; en-US)", you're probably tethering.
I and several others I know have been doing it for quite awhile and on several different kinds of handsets with no problems to speak of.
This is a recent thing. Be careful, confirm your carrier's policy. I tend to agree with the principle: You're paying for your bandwidth, so how you use it is none of their business. That's net neutrality. But the reality is that they want to get more money from you without providing any additional service, and they'll use their position of power to do it.