Ideally it's useful to pick a tethering friendly operator, although mobile providers that attempt to restrict it must usually rely upon some very fallible methods for determining whether or not a connection is tethered. Tethering itself is a local networking process so they can't detect that, but they can detect if you're doing something differently (e.g. using a different browser, using unusual ports to access the web, bypassing the operators proxy server erc.). Some operators might also require mobile devices to pass details of any tethered devices back to them.
Until recently there was a simple solution, go on to the android market and pick an "unofficial" tethering app. These do the same as your phones default one but most make it less likely that the operator can detect what you're doing. Google has now clamped down on this. Another problem is that such apps often require root access to your phone and that usually needs a bit of extra technical knowledge to sort out.
I think some of the apps around are:
Wireless Tether
PDAnet
Easy Tether
I think PDAnet, which has a free version, manages to do it without root.