This was quick relatively quick to set up, by following the guide here:

https://help.ubuntu.com/community/BluetoothDialup

The only catch was that I couldn't browse my Sony Ericsson z558i. Just make your phone discoverable and then try browse it, you'll get the MAC address, which you will need.

You can pair with the phone, from the phone itself. Ubuntu will come up with a dialog box for the pass phrase. (as I recall).

Only one technical step, which is to find out the RFCOMM channel

sdptool browse  your-phone-mac-address

Look for Dial Up Networking, there should be a Channel. On my phone it's 2.

Edit /etc/bluetooth/rfcomm.conf like this,

rfcomm0 {
        bind yes;
        device your-phone-mac-address;
        channel your-phone-rfcomm-channel;
        comment "Bluetooth PPP Connection";
}

Copy and edit the chatscripts given from the link to the guide.

For Digi users, this is the chat script:

TIMEOUT 35
ECHO    ON
ABORT   '\nBUSY\r'
ABORT   '\nERROR\r'
ABORT   '\nNO ANSWER\r'
ABORT   '\nNO CARRIER\r'
ABORT   '\nNO DIALTONE\r'
ABORT   '\nRINGING\r\n\r\nRINGING\r'
''      \rAT
OK      'AT+CGDCONT=1,"IP","diginet"'
OK      ATD*99***1#
CONNECT ""

From the command line, type:

pon BluetoothDialup

and you're on the way.

To disconnect:

poff BluetoothDialup