Carriers have the ability to analyze all data being routed through your device, including when it's acting as a hotspot. There are some rather simple potential indicators of tethering usage, such as
user agent strings, that can identify data being requested by devices other than your phone. I'm currently tethered off of my Galaxy Nexus, and when I load a webpage, my user agent is the following:
Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.11 (KHTML, like Gecko) Chrome/23.0.1271.91 Safari/537.11
The user agent is not the only information provided with an HTTP request. Look through the
HTTP request header fields for more information.
The two main reasons why you may be able to use your hotspot without the proper plan are because
1) you have not reached certain hotspot data usage levels/data usage types to constitute a warning or restriction, and
2) the carrier's current systems do not look for -- or are not capable of looking for -- your type of hotspot usage. For a period last year, Verizon's systems would flag unauthorized hotspot usage based on data upload statistics. Then, they employed specific monitoring systems for activities such as online gaming (think Xbox LIVE, not Words With Friends) and torrenting. Occasional minor hotspot usage was not a primary concern, as hotspot awareness wasn't as widespread as it is now.
For phones sold directly from a carrier, there may be software such as the infamous Carrier IQ installed. This is how unauthorized usage would be detected and reported client-side.
Edit: I should mention that it isn't necessarily as straightforward as I might make it seem -- it isn't always
easy for the carriers to detect hotspot usage, per se.