How to use your Moto Q as a modem

So, I have the awesome (and now-discontinued) Spring SERO phone plan, which basically gives me unlimited text/data/everything for less than I paid for Verizon's cheapest plan. The only problem I've had until now:

How to tether my Motorola Q phone to my computer, so that I can use it as a modem when I'm not in range of a wireless network?

I read a whole lot of stupid forum posts on this topic, mostly by seriously confused people, and I was under the mistaken impression that (a) it's really hard to do, (b) it requires special software, and (c) Sprint has removed the features enabling tethering from the phone.

Well, it ain't true. In the course of a few hours, I figured out not how to tether my Moto Q in two different ways: first, using a USB cable, and second, via Bluetooth. So I'm going to explain how to do it both ways under Ubuntu Linux 8.10. It should be pretty much the same under other Linux variants.