I'm posting this from my laptop sitting outside Marc's Karate dojo with my iPhone in my pocket providing my Internet connection over Bluetooth. I can't help but be geekily happy about this. I never bothered to set up the tethering before OS 3.0, so it's new to me. This is old news to the hardcore users.
I guess a new thing is that Fido is cool with the fact that I've tethered. Not that I care what they think, but phone companies are vindictive enough to actually cut you off if they detected you were tethering, so I feel a little better that it's legit. (Make sure you read the details to be sure you're legit.)
The best instructions I found are here. The instructions here show the actual commands, which is useful to know when you're debugging. It wasn't smooth for me because I didn't do the sequence in perfect order, and it looks like once I messed it up I just couldn't get it to connect. By going System-> Preferences-> Bluetooth and undoing the Bluetooth pairing, I was able to go through the steps from the start and get it working.
The part I had out of order is that I didn't check to see that the iPhone was actually connected to my laptop before attempting to tether from the laptop. The Bluetooth screen on the iPhone has to say "Connected", not just show the name of your laptop.
While writing this I lost my connection and couldn't get it back until I restarted Bluetooth on my laptop (sudo /etc/init.d/bluetooth restart). I have no idea what that's about, but I've seen others on the Internet complain that the connection isn't always reliable.