Não é muito difícil, eu faço isso com o meu. (Nokia N95 / Ubuntu 9.10)
- Primeiro, conecte o telefone com o cabo USB (não sei como fazer isso via Bluetooth),
- no telefone, escolha "PC Suite"
- no Ubuntu, clique com o botão direito do mouse no gerenciador de rede (o ícone no canto superior direito) e escolha 'editar conexões'
- Clique na guia "Banda larga móvel"
- Clique em "Adicionar" no canto superior direito
- Escolha seu celular da lista (ou o que for mais parecido)
- Siga as instruções para preencher seu nome de usuário / senha (se você não fez isso em seu telefone, não precisa agora - os padrões devem ser bons, mas isso depende do seu provedor de serviços)
Você pode definir essa conexão como 'auto', e sempre que você fizer o plug-in do telefone e clicar em 'pc suite' no futuro, a Internet simplesmente acontecerá.