Actually, it is very simple.. But let me clear something up.. did u mean WiFi Tether or Bluetooth Tether?
If WiFi is what u meant, then all Android 2.2 ++ will be able to do that.
It will act as WiFI AP (common hotspot) and PB will recognize and connect to it easily.
If Bluetooth tether. Then u just pair both PB and Android, and choose Internet Tethering on PB. Make sure u get the correct profile based on the carrier u use in Android phone.
I just tried this on my PB + GT-P1000 and it works! (both WiFi and Bluetooth).