Antes de mais, o seu telemóvel precisa de suportar a ligação Bluetooth. Onde encontrar essa configuração depende do seu telefone. Se acontecer de você usar CyanogenMod, seria em Configurações > Wireless & amp; Redes > Mais > Tethering & amp; ponto de acesso portátil > Tethering Bluetooth. Em outros sabores do Android, você precisaria dar uma olhada. Se você não tiver essa configuração, talvez consiga fazê-lo funcionar instalando um aplicativo. O Google Play tem algumas que afirmam que fazem o trabalho, embora eu não tenha tentado nenhuma.
Após garantir que o seu telefone suporta tethering Bluetooth, obtenha o Blueman (nos repositórios do Ubuntu). Com isso, você pode emparelhar seu telefone e o computador e usá-lo para conexão com a Internet.