Again, this is primarily a note-to-self. My normal internet connection is not always that stable, so I have to fallback to alternatives when things are suboptimal (massive packet loss up to 100%).

Before, I could use my Sony Ericsson C902 for tethering. With Bluetooth and a lot of PPP magic I barely understand, I was able to call my phone's modem and access the internet.

Fortunately, with an HTC Desire (and possibly with similar HTC devices), things are much easier. Connect your USB cable and select the network sharing mode on the phone. Then, on your Linux desktop:

You need USB network drivers in your kernel. The stock Arch Linux kernel comes with this functionality, but you might want to check this with other distributions or self-compiled kernels.