This is really just a checklist for me. Let me know if I forgot anything!

You'll need:
Motherboard
CPU
RAM
Video Card
Hard drive(s)
Sound Card
Network, although usually built into mobo nowadays
Keyboard and Mouse
Speakers
Monitor
CD Rom (DVD recommended)
Power Supply
Case

Stripping from another computer that you plan on replacing is usually a good idea, so you don't need to get everything and can save some money, especially if those parts really haven't seen significant technological advance since you bought them.

I am stripping:
DVD ROM
Mouse
Speakers
2nd hard drive
Sound card
Monitor

Make a checklist of what you plan to upgrade on the 2nd go, usually within a couple of months down the road.

I will, in the not so distant future, upgrade:
To dual 22" LCD displays and ditch my 19" CRT

Next, make a checklist of what you plan on upgrading further on down the road, like a year or two.

In a year or so, I will be upgrading:
Sound card to latest Dolby surround and EAX
Speakers to support latest Dolby surround (7 speakers or whatever it is now)
RAM
Possibly a 2nd video card because SLI is awesome.

Find the parts on a trusted website, like newegg.com, outpost.com, or tigerdirect.com. Place order. Wait.

When the boxes arrive, it'll be like Christmas and your birthday for the last 20 years of your life, all in one day. Now comes the best part. Building the beast.

Sloppily take out all the parts and throw them in a pile on the floor, making sure to remove the static guard from each piece, and allowing your dog and/or wool blankets to run over them a few times. Carefully place your mobo on the screw mounts in your case and screw it in. Connect the CPU, RAM, HDDs, Graphics and Sound Cards, and any other cards you won't need because this is a f@#%@$ing gaming machine. Connecting the pin connectors for the case is always the worst, and I just find out where the power switch and LEDs are and connect them, completely ignoring everything else. Who needs a reset button, or an HDD indicator? Certainly not me. Strap the power supply unit (PSU) up in there. Put your HDD and DVD rom drives in there before you start connecting them to the mobo. Connect the power cables to these components, and finally, plug in the power to the mobo.

Close the cover on your case, hopefully making it look like what it did before you took it off, but this is not important. Actually, the more f@#%@ed up it looks, the better. This is a goddamn gaming PC. Cut yourself and throw some of your blood on there, or if you can't be wicked l33t, just find a red marker. Glue with red sprinkles, red #40 food dye in a highly viscous liquid like shampoo, and ketchup all make convincing substitutes.

Connect your monitor, mouse, keyboard, speakers and network cable. If you have wireless built into the motherboard like some are offering these days, one of those steps can be skipped. If you have a bluetooth mobo and bluetooth keyboard and mouse, then a few more can be skipped.

Finally, plug the power into the PSU in the back of your case.

Hopefully all went as planned, and when you turn it on, you can immediately begin installing Windows XP (don't get Vista until all old games are supported, like Duke Nukem and Doom). Reboot. Install updated drivers. Reboot. Install the updates from 2002 to SP2. Reboot. Install SP2. Reboot. Install all updates from SP2 to current. Reboot. Note, you may have to reboot a few times for each set of updates. Install DirectX 10. Reboot. Install a game. Play!

You are finished.

Some notes on installation:
The CPU fan does not want to go on. Ever. But don't put too much pressure on the motherboard, especially if it's bending due to the position of the screw mounts. You might want to put the CPU and fan on before you put them in the case.

HDD masters and slaves are a pain. Get SATA HDD drives and an IDE DVD drive if you can. This will prevent much confusion. Get a big HDD (200+ GB) because you don't want to have to uninstall games to fit more on there. You only want to have to uninstall games because the game you are uninstalling happens to suck, or you got totally noobed online and can't bare to even look at the icon on your desktop. The uninstalling games because there's no room thing happens to me every time I get a new game. I have only 80GB and about 5GB left now that I uninstalled a few games that I won't be playing for a while.

Some other recommendations: 2GB ram is good for now. Dual core [insert brand name here] are good, and over 2 GHz is awesome. 700W PSU should be good for all upgrades over the next 2-4 years. Since DirectX 10 is out, get a DirectX 10 video card. Hopefully MS doesn't totally f@#%@ us over and upgrade to DirectX 11 before 2010. Sound cards built on Dolby 5 are great. 5 speaker stereo surround... who in their right mind would *need* more than that? You can save some money this way. I'm keeping my card which is 4 years old now, and my speakers which are 2 years old. Gigabit ethernet is the only way to go now.