I just spent hours trying to figure out how to do this since my cousin's desktop doesn't have a wireless adapter anymore. It's quyite simple actually.

Requirements

Jailbroken iPod/iPhone
iTunes
Your iDevice's USB cable
PDANet (Purchase through Cydia) - If you look around, you can find a "free" version. Don't ask where to get it.
PDANet Desktop (OS X Version, Windows x86 Version, Windows x64 Version)
A WiFi/3G Connection (charges vary with carrier)

Getting Ready

Before you even begin, your device must be Jailbroken. This is quite simple. If it is already JB'd, you can skip this step.

Click Here

Once your device is ready, purchase or download the trial of PDANet from Cydia. After it's finished installing, run it from the home screen. Tap settings and choose "USB Mode". Make sure your device is connected to your computer and leave it alone.

Connecting to the Network

I recommend using a WiFi connection instead of 3G (if available) mainly because it's faster and won't run up a bill.

Make sure that you have PDANet Desktop installed. Note for Windows users: A screen will pop up asking if you want to install the modem drivers. Make sure you click ":Install Anyway". After the program is set up, run it and an icon will show in either the System Tray or in your Finder bar. Click it and click connect. You should soon be connected through the PDANet modem and have an Internet connection.

A question regarding the whole internet sharing itself:

I have a iPhone 3G from T-Mobile Germany with a unlimited 3G data plan and my iPhone has a official internet sharing option, however when I click it, it asks me to contact T-Mobile first. If I use your method, could I get in trouble with T-Mobile? Since I pay for unlimited 3G I shouldn't but I feel like they would charge me horrendous fees

I'm not sure if T-Mobile supports tethering or not. I doubt they do but I also doubt that you'll get in trouble.

@ SchmilK: I tried using it but couldn't ever get it to work. The only problem with this is that it uses a weird IP and DNS setup. It still has the same speed as it does hooked up straight to your router or whatever you use.