iOS 4.3 and later

These instructions will work with iPhone 3GS and iPhone 4 with iOS version 4.3 or later.
You can check iOS version in Settings > General > About > Version
If your version is lower than 4.3 you can upgrade it via iTunes.

• On iPhone: Settings > Personal Hotspot > ON
  If you get a warning that Bluetooth is Off. Press Turn on Bluetooth
• On computer: Open Bluetooth Manager and add a new device. Exact procedure depends on Bluetooth software you are using. An example using DELL Latitude Bluetooth software:
  1. Bluetooth Manager > New Connection > Express Mode
  2. Select your iPhone from the list of discovered devices and click Next
  3. Double click on your iPhone name which now appears in Bluetooth Manager device list.
  4. Enter any passkey (e.g. 9561) and click OK
  5. On iPhone you should have a prompt to confirm the passkey. Enter the same passkey (e.g. 9561) and press Pair

You should be connected now. Pairing settings normally gets saved on computer and iPhone so next time you want to connect:

• On iPhone: Settings > Personal Hotspot > ON
• On Computer: Bluetooth Manager > iPhone > Connect

iOS older than 4.3

With iOS older than 4.3 procedure is similar, but instead of Personal Hotspot you need to enable Internet Tethering:
iPhone > Settings > General > Network > Internet Tethering > ON
Also make sure Bluetooth is enabled:
iPhone > Settings > General > Bluetooth > ON

If you have iPhone 4 with iOS v4.3 or higher it’s normally easier and more convenient to share your data connection over Wi-Fi personal hotspot.

Tested:
iPhone 3GS, iPhone 4
Windows XP
DELL Latitude