There is a story of an owner of a Nokia 808 who goes to Germany, sticks a German SIM into the phone, and Joikuspot works. Then he goes to the USA, sticks a US SIM into the phone, and Joikuspot doesn't work at all.
Now... how would that work?
I reckon that Nokia were pushed by the networks who resell their phones (and who account for the great majority of phones sold, I guess) to detect when Joikuspot is running, and somehow notify them.
Or Nokia detect the telco name and use a lookup table to determine whether it should allow Joikuspot to run.
It isn't done by switching to a different APN, for sure.
In fact when I start up Joikuspot, it offers the IPSEC VPN as one of the internet connection options 
The fact that I never got the damned VPN to connect to anything, it is blissfully unaware of.
And the other funny thing is that Joiku themselves told me the VPN "can't" be used...
I still think that "3" are detecting tethering the same way as the Iphone-contract retailers i.e. they set up the SIM card to tell the phone to set up a separate APN, to be used when tethering is used.
I would bet there is NO way for a phone manufacturer to get a phone into the high street shops in volume (which usually means branded by a network) unless they agree to support such a feature.
FWIW Peter, mine (iPhone 4s) was bought outright at the Apple Store (in the UK) and I'm on one of the various 'All You Can Eat Data' tariffs on Three. I'm pretty sure the info sent to the network emanates from the SIM card. When I use my iPhone in the US (on an ATT GoPone pre-pay plan that does not support data) and switch the data function on, I get an SMS telling me my plan doesn't support data PDQ.
I get an SMS telling me my plan doesn't support data PDQ.
OK; supporting "mobile data" is a different thing, and it is trivial to detect.
If you take a Virgin-SIM PAYG phone outside the UK, and e.g. try to retrieve email, you get a few hundred bytes and then they cut you off, and you get an SMS telling you that to get data you need to buy an EU data bundle, for £X for Y MB, and you get several options (which, with Virgin these days, are all outrageously pricey, but it is an OK solution for a day trip to LTQ).
Some "interesting" stuff:
In Greece (Zakynthos) recently I was able to get data OK on my Nokia 808 contract (SIM-free unlocked) phone. I was also able to get data on a very old PAYG SIM in a 3G-equipped Thinkpad laptop, using the "Vodacom" software which came with the laptop. But ...
(1) If the phone was within Vodafone coverage (Vodafone GR) I could not get Joikuspot (a wifi tethering app) to work. It would say there is no mobile data.
This is the issue they are finding in the USA where JS is not included with the phones, and even if you install it (or buy a completely non-US-market phone) it still won't run, in general. It looks like Nokia, and presumably others like Apple, have implemented some very specific mechanism which enables the telco to detect that a specific tethering app (which on a Nokia has to be JS; nobody else has done one AFAIK) is running. In the case of an Iphone, as mentioned above, the phone uses a different APN when tethering, so they know anyway, but JS uses the same APN and can even use a VPN connection (assuming you can get an IPSEC VPN to work on the Nokia, which I have not been able to do so far).
(2) If the phone was tethered using bluetooth (to a Lenovo win8 Tablet 2) that worked fine, which proves that Voda are not doing packet inspection, but rather they "know" straight off that JS is running... somehow.
(3) Putting a Cosmote data-only SIM (2GB for 10 days, €15) into an E585 3G-wifi modem, which is normally the best way by far to get data on holidays to places where such SIMs exist, worked but not with Vodafone GR. In this case Voda GR are blocking a bona fide Greek data-only SIM, which is outrageous.
It thus looks like Voda are getting onto the act played out in the USA, where you are given X MB monthly allowance but then they implement measures to stop you actually using it, other than by downloading data onto the phone itself (most people won't know how to use bluetooth, and it doesn't work with Apple stuff anyway, for data).
It is pretty trivial to see when a user is tethering, the 'trouble' for the telcos is that, under privacy EU regulations, they can't. Any kind of web access will just say 'hey, I'm device type such-and-such.'
Could you elaborate on that?
It seems obvious they can tell when the traffic is probably not being generated on the phone, but it seems equally obvious that any method they can use in an automated manner is going to generate a lot of false positives (i.e. false allegations of tethering).
The indications I have seen suggest that whatever they are doing detects tethering almost immediately.
The most obvious place is in the HTTP request headers. They're allowed to route all your requests through their transparent proxies to speed up the network (you'll find this in your contract somewhere). One of the http headers is the User-Agent. Your phone will say one thing, including iOS version or android version. Your PC web browser will say MacOS, Windows version or Linux version.
You can change that, but it's tricky to get right - plus you'll get all the mobile sites on your laptop... not what you want.
If you want to go stealthy, use one of the VPN services which tunnel through the HTTPS port 443. They'd still be able to see something is amiss, but it could just be a corporate app.
I have just seen another curious one:
Sitting near Innsbruck, Vodafone phone (Samsung S6), roaming on a local network called “AT”. Tethering the phone to a T705 tablet.
The network detects it and after a minute or so cuts the data.
But only if I tether via WIFI. If I tether via Bluetooth, it doesn’t detect it. I saw the same in the Nokia setups. Clearly the phone reports tethering but only if acting as a wifi hotspot. In the Nokia world the phone used to report that Joikuspot was running.
One can’t prove it and the networks obviously don’t discuss it but it is pretty obvious. Google must have done a Nokia type deal with the networks to covertly return the phone’s hotspot status. Apple do the same but I don’t know if Bluetooth tethering avoids the issue.
All the original iPhones can be used for tethering. I even used it last week at my home office with my desktop Mac when the internet was down for a day. It works with my iPhone (Vodafone) and my wife’s (t-online) as well. we never had a problem with it in Greece. My wife also uses it with the iPad mini, because she has one without a SIM.
EDIT: Every phone company I asked about it in the past told me that “while they don’t like it”, they can’t do much about it. It’s only four days ago that Vodafone told me that on the phone when i changed my contract.
Nearly all phones can be used for tethering but that is not the question.
