Until the default Gnome / KDE Bluetooth and networking applets gain better support for tethering a mobile phone wirelessly for a GPRS connection, I recommend installing Blueman.
Your wireless telephone service provider possibly charges exorbitant rates for Internet access. Please ensure that your wireless data plan includes a high enough quota that you will not be unpleasantly surprised when you see your next bill.
See https://edge.launchpad.net/~blueman/+archive/ppa for details on adding the appropriate repository and key.
sudo apt-get update
sudo apt-get upgrade
sudo apt-get install blueman
Apt will automatically take care of removing conflicting Bluetooth applications.
With Blueman installed, go to whatever startup applications manager is appropriate for your flavor of Ubuntu (in XUbuntu it's in the Applications menu --> Settings --> Session and Startup, on the "Application Autostart" tab). Disable the default Bluetooth applet configured as an autostarted application, and add blueman-applet instead.
The Magic Show
With your phone paired (search this wiki if you can't figure out how to pair your phone), establishing an Internet connection through your phone when tethered via Bluetooth is amazingly simple.
1. Single left click the Bluetooth icon in your notification area (next to the clock) to launch the Bluetooth Devices window.
2. Right-click on your phone entry and go to Serial Ports -> Dialup Service.
3. The first time you do this, you'll get a dialog asking for clear, idiot-friendly information regarding your wireless service provider. Just tell it whether you use AT&T, Verizon, Sprint, or whomever.
4. Once your computer connects with your phone, single left click on the Network icon in your notification area, and you'll see a new entry for "Mobile Broadband." Click it to activate it, then listen to the thunderous applause in your head.