This method is for the homegrown type who don't have or want to shell out $100-$300 for a fancy new wheel set, and don't mind a rough-around-the-edges look. I would not recommend taking this step if your bike is valuable or you think you might be selling it any time soon.
Also for any cyclists who want to learn how to unbuild and rebuild a wheel, this instructable will take you there, just skip the masking and painting steps.
I used a rear wheel, 27" 36 spoke, 3 cross setup for my demonstration, but most steps will be the same for other sizes or spoke numbers and configurations. If you are using a front wheel, it will be easier because you won't have to worry about different spoke lengths and dishing.
Hope you have fun and learn something here!
Step 1: Wheel Disassembly
1.) [Deflate tire first, then]Remove tire and tube--using a tire lever or screwdriver (use caution so as not to rip/puncture the tube), pry the tire off on one side of the wheel, then work your way around. You will probably need to use to levers and work against each other. Once the wheel is half off, peel the tube out from inside it, using care when removing the valve stem from its hole. Then the other side of the wheel should come off relatively easy
2.) Take spoke nipples off--Using a spoke wrench or screwdriver, start by loosening the tension on all the spokes evenly, to avoid "potato-chipping" the wheel (i.e. uneven high pressure spokes distort the shape of the wheel into a non-round shape). Then keep going around and remove all the nipples from the spokes and collect the nipples and spokes in a place where they will not get lost/damaged/dirty. If you are working with a rear wheel, make sure you keep the inside and outside sets of spokes separate, as they should be different lengths.
You should now have an empty rim, all your spoke nipples, your spokes, and an empty hub, and this is the perfect time to give them all a good cleanup, especially to prevent nipple-spoke seizing.
Step 2: Bill of Materials
Materials for lacing/building a wheel:
1 hub with (36) holes total on both sides
1 rim with (36) spoke holes, plus one wider valve stem hole
(36) spoke nipples
*the number in parentheses can be a different number, just make sure it is the same for all parts
**if you are using nipples that are not new and may have some corrosion, it is a good idea to soak them in some solvent (biodiesel, gasoline, other metal cleaner) to get all the gunk off, and to ensure they will spin freely on the spokes in the future
Materials for painting:
1 can of spray paint (I use flat black, cheap brand, but if you want to be fancier, go to an art store and buy a nice color)
Masking tape (I actually use scotch tape, but other kinds will work, as long as they don't leave glue behind)
Cardboard or newspaper for painting surface (be careful of overspray, spraypaint goes everywhere!)
Spoke Wrench (if your spoke nipples have a screwdriver slot on the back, you will be able to do it pretty much all with a screwdriver instead)
Tools for Cog/Cassette removal (varies widely between bikes, but cog or cassette must be removed to get spokes in and out)
Truing Stand/Bike frame (if you don't have access to a truing stand, you can get it more or less true on your frame)
Step 3: Painting
Use scotch tape to mask the sides of the rim (braking surface) so the brakes will not get all gummed up with paint
Mask the threads of the spokes, so they will screw into the nipples smoothly and not gum up or seize
Spread out newspaper or a big piece of cardboard to protect the ground from paint, then lay out all the spokes with the heads all pointing the same way. After painting the first side and letting them dry for at least 15 minutes (depending on temperature, wind, etc.), roll them so the heads are all pointing the other way, then paint the second side. Try to get the spray paint in at an angle so that you get all sides of the spokes.
For the rim, stand it up with one hand and spray the bottom from the inside of the rim, towards one side of the tape, to get as close to the tape as possible. Turn the wheel and paint as you go, then when one coat has dried, flip the wheel and paint towards the other side of tape.
When all paint has sufficiently dried (wait longer this time, ~30-45 minutes, so that you will not mess the paint up when working with the parts), you can go on to the rebuilding process.
Step 4: Install the First Run of Spokes
Take one spoke and put it through a hole in the rim and loosely twist a nipple on to the spoke to hold it in place. Only twist each nipple on to the spoke enough to hold it (5 turns or so) so you don't get too much tension too soon.
Working around the hub, take the next spoke and do the same thing in the rim hole four spaces over from the first one. Continue until all the spokes are attached to the rim with spoke nipples. You should have three open holes between each set of spokes.
Step 5: Install the Second Run of Spokes
The second run should be in holes on the rim directly adjacent to the first run, and once again, in every fourth hole. The holes in the rim should be half filled now, in a pattern of 2 empty, then 2 filled, then 2 empty, etc.
Step 6: Install the Third Run of Spokes
This is where it gets a bit more complicated. Take the hub and twist it in the rim, so that you tighten up all the spokes and they meet the hub at an angle (see picture). If you are doing a 3 cross pattern, the new spokes will go over the first two spokes they cross, then under the second, and will be two holes away from the last spoke it crossed. The third run spokes should be making a big X with the first run spokes, starting six holes apart on the hub, crossing, then ending two holes apart on the rim. If you are still a bit confused, try looking at different picture and trying to get a view of it.
Step 7: Install Fourth Run of Spokes
Step 8: Tension and True the Wheel
Start by hand tightening the spokes all about four more twists, and this is where you need to make sure you start at the valve stem hole and end there, so you tighten all spokes evenly. Once you can't hand tighten any more, go around and give each spoke 1 or 2 full turns with the spoke wrench, unless they are already quite tight. If you think the tension is high enough, begin truing.
Give the wheel a spin and look for spots where it bumps out to the side (putting your finger or a stick next to the wheel so it hits it is a good indicator). If the rim wobbles to the left in one spot, loosen the spokes on the left side in that area (2 or 3 next to it) and tighten the spokes on the right side. Only tighten about 1/4 turn at a time, so you don't overdo it.
If you have more question, or are confused about anything, just leave a comment or check out http://www.sheldonbrown.com/wheelbuild.html Sheldon Brown's cycling pages are the best source on the interweb for bicycle stuff.