OK so the iPhone doesn’t use your computers internet when connected via USB. Why? I dunno it’s one of the sadly lacking features on an otherwise awesome device.
Sharing the net however via ad-hoc wifi is easy. In System Preferences, go to “Sharing”, select Internet Sharing (don’t tick it yet), tick ‘Airport’ then tick ‘Internet Sharing’.
After you’re done – go into the Network Settings -> AirPort, and create a new network with a password (to stop those leechers). By default it is shared without a password which is dangerous (unless you’re in the desert or something). This new network should have the sharing on it if you did it right – but go back to the sharing tab and double check that it’s still enabled. Then on your iphone connect to your new ad-hoc network and enter the password.
Update: at least in Snow Leopard there is a button on the Internet Sharing settings named “AirPort Options” which allows you to setup the Wifi password in a better (more permanent) way than the one I described.
Update2: I have had some issues with sharing certain networks in Hotels – the iPhone can connect to my computer, but not the internet. One option is to install the proxy server Squid. This isn’t easy, and unless you are a developer with bash experiance I don’t recommend it (if you know what you are doing though it’s easy – just install the unix build tools, download squid, then ./configure, make and run it… default settings are fine – and just set the proxy IP in the iPhone to be that of your computer)
If you have no Wifi card (e.g. on a PC) then bad luck. If you’re on windows I’ll leave it up to you to figure out I’m sure there’s a way :-)