I wanted to access the internet over bluetooth instead of GPRS/3G network from my mobile phone (SE K800i). After a lot of searching I couldn't find a clear explanation as how to accomplish this. I did manage to set it up with Windows XP, using the "Personal Area Network" in the bluetooth utility and doing internet connection sharing. After another fruitless search, I managed to figure out how to make a bluetooth internet profile instead of GPRS or 3G on the phone. Since I work in Linux most of the time, I decided to have a go and do it with Debian, my workstation's main OS. After spending a few hours, I had it working using the steps below.