This tutorial is written for those who are not familiar with Ubuntu/Linux and is very detailed. If you are experienced feel free to just grab what you need from it.
Update: I've updated the tutorial to fix some errors that came up due to a change in the libiphone package.
Update (1/27/10): I've updated the tutorial with a new PPA and set of packages needed for tethering via USB to work. This should iron out all other problems with the tutorial.
Tethering the iPhone via Bluetooth is as simple as pairing the two devices and ensuring that Internet Tethering is turned on on your iPhone. To pair the devices you will need to install a new Bluetooth manager aptly named "blueman" from the Blueman Project PPA repository. To do this you will need to execute the following commands in a new Terminal window:
sudo add-apt-repository ppa:blueman/ppa
sudo apt-get update
After it finishes updating your repositories you can install Blueman by executing
sudo apt-get install blueman
Once everything stops working and you're back at a blank command prompt you can then close Terminal and open the "Bluetooth Manager" which can be found in the "System>Preferences" menu. (Note: A reboot may be needed for it to open) To pair the devices you will need to turn on Bluetooh on your iPhone and computer. To turn it on on your iPhone open the Settings application from your springboard, when the settings screen appears press the "General" button near the bottom, from here press the "Bluetooth" button, and then press the switch to turn it on. Once on you should see a list of devices as well as a message near the bottom saying that it is "Now Discoverable". In the "Bluetooth Manager" program press the "search" button and the list should be populated with nearby discoverable Bluetooth devices. Locate your iPhone 3G(S) from the list, select it, and press the "Keys" (pair) button above it. At this time Bluetooth Manager will attempt to pair the two devices. On both the iPhone and your computer you should see a prompt asking you if you want to pair the two. Press "Pair" on your iPhone and "Yes" on your computer. Once paired, press the diamond on Bluetooth Manager to trust your iPhone.
Now that everything is set up, you can go back into the "General" tab on your iPhone's settings and select "Network" near the bottom you should see "Internet Tethering" (if you don't then you need to install the proper carrier profile to enable it) press on it and turn it on. Lastly, go back to the Bluetooth Manager program on your computer, right click on your iPhone and select "Network Access Point" from the option "Connect to:" it will work and hopefully give you a "Connection Established" message. Your iPhone should now have a blue banner with "Internet Tethering" on it. If all went well, you should now be able to access the internet through your iPhone's data connection.
Thanks to Sergey Stadnik Bluetooth tethering on 10.4 (Lucid) now works. According to him: "... right-click on the Blueman icon, select Plugins. Enable NMPANSupport plugin, press Ok."
Tether via USB:
Tethering your iPhone via USB uses a iPhone Ethernet driver written by Diego Giagio. Paul McEnery has set up a PPA repository with the driver and it's dependencies so there is no longer the need to compile both ‘libiphone' and ‘ipheth'. The first step is to add the PPA repository to your Synaptic repositories. To do so, open a new Terminal window and execute the following command:
sudo add-apt-repository ppa:pmcenery/ppa
sudo apt-get update
Once it finishes updating you can continue by downloading and installing the driver and the needed dependency:
sudo apt-get install gvfs ipheth-utils
When it finishes plug in your iPhone via USB, if internet tethering is enabled you should see a new interface pop up and a blue banner on your iPhone along with a dialog on your computer notifying you about a new ethernet connect. If not, check to see if tethering is enabled by opening the Settings application on your iPhone and navigating to "General>Network", near the bottom you should see "Internet Tethering" (if you don't then you will need to download and install the proper carrier profile) press on it and turn it on. Open up a browser and enjoy your mobile internet.
Hopefully, you ran into no errors with this tutorial. If you did let me know, or let me know if you ran into any error with anything else pertaining to it.