Step 1: What Do I Need to Build a Laser?

Basically, you need:
laser diode (LD)
collimation optics
current regulator (aka driver)
power supply
heatsink
something to house all the electronics (project box is ok for a first build)

then you can add other optional things:
safety switch
LED for power indication
cooling fan
etc...

Step 2: What Tools Do I Need?

You need:
soldering iron
solder
DMM (digital multi meter, even the cheapest works fine)
some wires (the more flexible the better)
small pliers

other useful tools:
tweezers
vice
3rd hand

Step 3: Step 1: Gathering the Laser Diode

Here you have 2 options:
either to get a DVD drive for pc and extract only the diode assembly (aka sled).
or buy just the laser assembly from the internet.

You can get old DVD RW drives on ebay for >15usd, or just look around and ask friends if they don't have some old unused drives.
The another option is to buy just the sled ftom internet.

My favourite e-shops for laser components:
http://modwerx.com/shop/
http://hightechdealz.com/
http://stonetek.org/shop/
on these sites search for LPC-815, this is the most commonly used red laser (22x write speed).

What if I can't find the LPC-815, if I have only 20x or 16x burner, or if I'm not able to determine the write speed?
First, use google to find out something about your drive (search for part numbers from the label), this should bring out enough information. Remember the write speed.

You must extract the diode from the sled. This video shows the process:

if you have other model of dvd burner, set your DMM to the DIODE TEST mode and test both diodes using the pinout below. When you see bright red light, you've got your diode :)

Step 4: Step 2: Collimation Optics

This is needed to make the actual laser beam. Without this lens, you would have just a very wide, useless spot.
The most common colimator is called Aixiz module, and it serves as the holder for both the diode and lens.
The diode is being press-fit into the module, using vice (see the pics).
You can buy it from the e-shops I mentioned in previous step

Step 5: Step 3: Driver

What's this?
This is used to regulate the current flowing through the diode.

Do I need this?
YES! You must NEVER connect the LD directly to the power supply because it WILL die!

Can I just use a resistor?
Theoretically yes, but the current will not stay constant as the components heat up and the battery voltage decreases and this can shorten the diode's life.

But kipkay didn't use any driver...
Why do you think we have to deal with n00bs crying about their dead Laser Burning Flashlight Hack? (Just read the text above...)

UPDATE
A lot of people ask me about the diode's forward voltage stuff. This is a constant current driver. That means, it will adjust it's output voltage in order to keep the optput current fixed. So, it doesn't matter if you connect a red (2.2V), IR (2V), 405nm or a 445nm (>4V), as long as your power supply's voltage is above the diode's voltage + 1.5V, your laser will be running fine at the set current.
Also, the answer to question: "What voltage is diode XY?" can't be answered directly. Every diode's forward voltage (Vf) depends on her type and on the current. For example, a LPC-815 has Vf from 1.8V up to about 3.2V, as the current increases. Every diode has a PIV plot, which describes it's dependancy between the current, optical power and voltage. Google your diode's PIV plot, such as "LPC-815 PIV" or "22x red PIV" and so on.
Since we're building a red laser here (based on LPC-815), here's the PIV plot for LPC-815: http://www.diy-lasers.com/images/LEC_LPC-815-red.png

You can either buy one or build one (if you can)
the most common commercially sold drivers are:
http://www.modwerx.com/shop/laser-diode-drivers-test-loads-c-10/adjustable-laser-diode-driver-circuit-assembled-red-or-blu-ray-p-8?zenid=heee48kk0ak9008r2v8oo60cn7
and
http://laserpointerforums.com/f64/lava-micro-flexdrive-driver-lavadrive2-fits-pens-22502.html (usage instructions: http://hacylon.case.edu/ebay/laser_diode/MicroFlexDrive_V5_manual.pdf)

The most common DIY driver is called DDL driver and it uses LM317 as current regulator.

you will also need a thing called TEST LOAD, which consists of 4 1N4007 diodes and 1 1ohm resistor wired in series (check the pics). To use it, connect the output terminals of driver to test load (+ on the diode's anode, - to the resistor) and measure the voltage across the resistor. With 1ohm resistor, 1mV of voltage equals to 1mA flowing through the setup. Now rotate the small potentiometer, until the DMM reading matches your desired current.

recommended currens for various diodes:
16x...200-250mA...<200mW
22x...300-400mA...250-300mW

Step 6: Step 4: Power Supply

Most beginners use 9V battery to power their first build, but 9V batteries have very small capacity and can't supply high currents (>350mA) for long times. Laser with 9V
battery at 350mA will burn for the first 60 seconds or so and after that the laser stays at <100mW and can't burn anything.
Now you must decide, if you want to build a portable laser or "labby" style, which just sits on the desk, powered by wall PSU.
The second option is easier, any wall PSU that puts out at least 8V at 500mA
If you want a portable build, the best option is to use Li-Ion batteries. The most popular are the 18650 's, but there aren't any battery holders for 18650, so easier is to use
14500 (AA size) or 10440 (AAA size), which can be used with standart AA/AAA holders. Don't forget to buy a proper charger .
Now, just connect it together using the schematic below. Pay attention to the pinout, if you connect it wrong, the diode WILL die

Step 7: Step 5: Final Phase

The last thing you need (or you should have) is the heatsink. Just find some small heatsink (good heatsinks are usually inside old CRT monitors), on which you can easily mount your laser module. Thermal epoxy (like Arctic Silver) is your friend :)
Or you can buy this one: http://www.laserlands.net/heatsink-12mm-yh.html

Now, let your imagination take over and build all this stuff into some nice project box.