Technically, it's not illegal as you aren't changing the phone or using your connection to the net any differently, just routing it to a different client.
I've used tethering on Android extensively and it works very well. I used to have an HTC Hero which only supports wired tethering (phone as modem) but newer models such as the Droid X (it's awesome) support wireless tethering (phone as router).
Unfortunately, I cannot discuss the means by which wireless tethering is achieved on the Droid X as it would be a breach of the terms here on BC.
I can however tell you how to achieve wired tethering as it does not involve modification to the phone...
Go to this website... My link
Here, you will be able to download a free or paid version of PDANet. PDANet is a tethering application for smart phones. It works for certain versions of iPhone, Android, Blackberry, Windows Mobile and a few others.
Click on the icon associated with your phone/operating system type and you will be taken to the appropriate page. Confirm that the app supports your operating system version and download the app to your computer.
You will also need to download PDANet from the marketplace.
NOTE: I've only done this for Android so I do not know if it is on the Apple Marketplace. I'm not sure how to do it for Blackberry or Windows Mobile either.
A google search will most likely reveal anything you need for non-Android users.
The free version will only allow you to visit HTTPS websites for 10 days but you can access HTTP websites all day long! The paid version allows you to access both HTTP and HTTPS unlimitedly. The app is relatively cheap for what it does and I recommend coughing up the cash for it as it is a GREAT APP and you'll be supporting the people who WORKED REALLY HARD to produce it.
Once you have downloaded PDANet on your computer and your phone, you are ready to start tethering.
Use the usb cable that came with your phone and connect it to the computer.
Enable USB Debugging on your phone.
On the phone, launch the PDANet application and press the Enable USB Tethering
button. This app will run in the background so once you've started the process you can back out of this. Just don't forget to turn it off when you're done as it will consume resources even while not in use.
Now that the phone is ready to tether, start the PDANet app on your computer (PDANet should already be running and can be accessed through a tray icon in the system tray. The system tray is in the bottom right hand corner of your Desktop by the clock.)
Click the PDANet icon in the system tray and select the Start Tethering
The first time you do this, it will take a few moments while it installs the driver. If it can't find one, you can download the driver from your phone manufacturers website and put it anywhere (the desktop is fine).
There, you are now connected to the Internet using your phone as a modem.
NOTE: The phone must be ready to tether before the computer is. If you ever have a problem getting it to work. Try turning PDANet off on both computer and phone, unplug the phone from the computer, Enable USB Tethering, reconnect the phone to the computer and then Enable Internet Connection on the computer.