I found this page that sends you via email the right "Profile" for iPhone 3.0 to enable tethering.
No Jailbrake or Unlocking required: it just works.
After you install the profile, enable Tethering and follow the instructions on the phone. If you decide to use Bluetooth, after you pair the device with your laptop, just configure it as "network port" (on Mac it will be almost automagic!).
Performances are pretty good, I must say.