The carrier settings bundle for each network in iOS (either built in or downloaded as updated carrier settings) includes all the settings that relate to Tethering.

The way most networks control Tethering access is by specifying a different APN for Tethering data and Phone data in the carrier settings bundle. Then to disable Tethering on the account they just disable the Tethering APN at the network end. If the phone tries to activate Tethering and the network rejects access to the APN the button is removed in the UI. Each time you go into the Tethering page under General->Network the phone will again attempt to activate the Tethering APN - if it succeeds the button is re-enabled in the UI. Simple as that...

Up until 3.1.3 it was possible to customise the carrier settings bundle (including custom Tethering APN) and upload it into the phone, now all the APN settings are signed by Apple so its not possible to do so.

For most networks they can tell that you're Tethering simply because the data is going through a separate APN - for those networks there is no way to "fool" them into thinking you're not Tethering when you are - they know for sure that you are.

Three are an interesting exception. For reasons that elude logic, they use the same APN for both Phone Data and Tethering Data, in fact even on an Android or other device its not possible to open a second data APN at the same time, and it has been like that for over a year. Because of this iPhone Tethering works on all Three plans whether you have a Tethering add-on or not, and its difficult (but not impossible) for them to know that you are Tethering.

The only way they can tell is by looking at browser user agents or otherwise analysing the traffic, meaning you typically get away with it if you don't abuse it.

I'm still on 3pay Pay&Go and although I don't use it much I've tethered both with the 1GB Internet max addon, and with the free 150MB blocks of data with topups and never had a problem or any warnings not to do it.... but then I haven't downloaded GB's of data.