I think you do not need tethering, but something similar to http://www.howtoforge.com/bluetooth_pand_debian_etch
The setup could be simpler if you use static ip addresses instead of dhcp.
In summary you have to set up ip over bt and 'nat' out into the internet.