Simply turning on tethering in the preferences doesn't turn on the blue bar - you have to connect it with a computer via Bluetooth or USB for it to work. Seeing as you've tagged this "osx", I'm assuming that you have a Mac.
The most reliable way to get my phone to tether is with USB. The first time you connect it with tethering enabled, your Mac should tell you that it detects a new network device, and will ask you if you want to configure it. The default settings (automatically get address via DHCP) are fine, and it should begin to tether.
If this does not happen, you could try Bluetooth, but there have been issues with the unibody Macbooks and the iPhone Bluetooth tethering, but it's worth a shot. To do this, you have to select "Set up Bluetooth device" under the Bluetooth menu in the top bar. When it asks you what kind of device you're setting up, you need to select "Any device". The iPhone does not show up if you select "Mobile phone".
At this point, you need to turn on Bluetooth discovery on your iPhone - this is accomplished by navigating to the Bluetooth preference pane in Settings - you will see "Now Discoverable" at the bottom. Your Mac should see your iPhone as a Smartphone, and after you bond the two you can select "Use device as a network port" and complete the setup.
Now, when you go to the Bluetooth menu in the top bar you will see your iPhone, with a submenu item to "Connect to network". Selecting this should be enough to get it to tether. (This may take a few tries).
At least, this is how it's supposed to work. Can you be more specific about which step you're stuck on?
I personally find that bluetooth doesn't work too well, but great advice on the USB connectivity! – Alexis Hirst – 2009-08-01T22:29:46.753
Sorry for the delay in accepting. I was having problems because I was not selecting "Any Device" when setting up via bluetooth. Cheers buddy! – EvilChookie – 2009-08-03T23:44:10.810
+1, great answer. Bluetooth doesn't work reliably for me either, it just craps out at random. USB, on the other hand, has been excellent. – Pauk – 2009-08-08T20:17:57.543