Been meaning to write this one for a while, specially now Sam helped me solve both connection problems I was having in one go without even knowing it. So if you follow this guide and you should be able to do most of what you want with the windows mobile phone.
However there is a problem with some phones like my TouchHD. They have the wrong MTU setting and this sometimes depending on how you got your machine setup can make it unresponsive when trying to access the web. So if you have the problem of being able to ping but not access the web correctly now check the MTU size. I also got everything working with Bluetooth too instead of USB but its a lot more complex and battery life becomes a problem when you got Bluetooth on for 3 hours straight during a train journey.
Tethering on a Windows mobile phone is pretty simple and as far as I know its pretty much the same on Windows and the Mac. I know you can get those USB dongles but do I really want another contract? Not really thanks. Its a shame that Microsoft didn't give this platform much more attention because its actually pretty good in parts. I mean I couldn't imagine buying a phone which can not be tethered for internet access and mass storage.