How they detect that someone is tethering a device isn't something that network providers often want to talk about, for the obvious reason that the more consumers know about how this is being detected, the easier it is for them to find ways to hide the fact that they're doing it, and avoid the associated extra charges (1). However there are certain known techniques that will give away the fact that you're currently tethering, if your Service Provider happens to be running the right tool to check for these indicators:
Your Phone asks your network if tethering is allowed
The first and easiest method is that some phones will query the network to check whether the current contract allows tethering, and then totally disable the tethering options on the device in software if not. This generally only happens if you are running an OS version that has been customized by your Provider, example 1 example 2.
Your phone tells your network that you are tethering
It's also rumoured that some phones have a second set of APN details saved in them by the phone network, when you enable tethering they switch over to using this second APN for all tethered traffic, while using the normal APN for traffic originating on the phone. However I haven't found any concrete evidence of this, other than people finding odd APNs and wondering what they're for (bear in mind that an unlocked phone bought off-contract may have hundreds or thousands of APNs stored on it, ready for use on whichever network in whichever country the eventual owner decides to use it).
Inspecting the network packets for their TTL (time to live)
Every network packet travelling across a TCP/IP network, like the internet, has a built-in time-to-live (TTL) set on it, so that in case there is a problem with that packet reaching its destination this will stop it travelling around the network forever clogging everything up.
The way this works is that the packet starts with a TTL number (say 128) set on it when it leaves the sending device (your phone, or laptop), and then every time that packet travels through a router of any kind (like your home broadband router, or a router at your ISP or phone company) that router subtracts one from the TTL (which would decrement the TTL to 127 in this example), the next router it travels through will in turn decrement the TTL again, and so on, if the TTL ever reaches zero then the router it's at discards the packet and doesn't transmit it again.
When your phone is tethering it acts like a router so, as the packet passes from your tethered laptop through your phone and onto the phone network, your phone will subtract "1" from the TTL to show that the packet has passed through its first router. The phone networks know what the expected TTLs from common devices are (for instance packets from an iPhone always start at a TTL of 64), and so they can spot when they're one less (or totally different) than they're expecting.
MAC address inspection
Devices on a TCP/IP network, like the internet, all have a unique MAC ID set on their network interfaces. This is made up of two halves, one half identifying the manufacturer of the interface, and the other half being a unique identifier assigned by the manufacturer (like a serial number). Every network packet that is sent out will have been "stamped" with the MAC address of the originating device's network port. The MAC address of your laptop's wifi card will have a very different manufacturer and serial code than the MAC address of your phone's 3G interface.
Different computer Operating Systems (eg Android, iOS, Windows, Mac OSX, Linux, etc) set up their TCP/IP stacks with different default values and settings (eg the Initial Packet Size, Initial TTL, Window Size...). The combination of these values can give a "fingerprint" that can be used to identify what operating system is running on the originating device. A side-effect of this may mean that if you're using an uncommon OS, or an OS that's similar to your phone's on your other device, your tethering may not be spotted.
Looking at the Destination IP/URL
You can learn a lot by what a device regularly communicates with.
For instance, many OSs these days do Captive Portal Detection when they first connect to a wifi network (such as your wifi tether connection), they do this by trying to connect to a known web server across the internet, and checking to see if they get the response that they're expecting. If the expected response is not received, then it's likely that the wifi connection you're on is a "captive portal" and may need you to log in, or pay, to connect to it. As Microsoft OSs (like Windows Vista and Windows 7 check with a Microsoft server by default and other OSs like Android, MacOS and so on all connect to their parent company's servers to do these checks, it can be used as a good indication of the operating system just after the initial connection is made.
Additionally, if a device regularly contacts the Windows Update servers, then it's very likely that device is a Windows PC or laptop, whereas if it regularly checks with Google's Android update servers, then it's probably a phone. Or if they can see that you're connecting to the Apple App Store, but the IMEI of the device that your SIM card is in indicates that it's not an Apple device, maybe you're tethering an iPad to an Android phone?
More sophisticated systems can look at a whole range of data seeing who you're communicating with (eg are you connecting to the Facebook app's API servers which is more likely from a phone, or to Facebook's web servers which is more likely from a PC) and add a whole load of these indicators together to create a fingerprint that indicates what sort of device you're likely to be using. Some of these fingerprints can be caught out when new device types and services come out, for instance there are reports that just after tablets with built-in 3G came out, some owners of these on the AT&T network received mails warning them that they'd been tethering when they hadn't, as the fingerprint from this new style of device didn't look like a typical phone.
(1) Obviously before trying any methods to by-pass tethering detection please remember to check your phone contract and your phone company's policies on tethering. They may have penalty clauses buried in their contract, Fair Use Policy, or Acceptable Use Policy for people who try to bypass their restrictions and limits.