Quite intimidating task at first glance, but it's not actually difficult, may even be fun. First wheel I ever tried to lace came out double instead of triple crossed, then I had to file down spoke tips to prevent punctures, and now the wheel is still in service. Second wheel was better, but I messed up the crossing order and it was not very strong. After third re-truing I lost patience and remade it. Next wheels were OK. First two attempts at calculating spoke length ended with their exchange, last six were correct. I'll try to describe my proven process.
Spoke length is measured from the inside of the bend to the end of thread: 
Spoke pattern is a three-dimensional geometric structure that can be split into triangles solvable by standard high school geometry:
Used symbols:
If you are not a fan of manual calculations, use this Excel sheet or this online calculator (both use the formula above):
The calculator is written in Javascript and doesn't need an internet connection to work, so you can save the page to your computer for offline use. Other units than millimetres are possible, they just need to be the same in all fields. Calculation occurs automatically after changing any field's contents and clicking elsewhere.
The number calculated in previous paragraph is the theoretical distance between centrepoint of hub spoke hole to the inner surface of the rim. Real spoke must be a bit longer to reach through a rim hole and screw into a nipple. How big bit? The safest method is a real-world measurement again - see the picture on the left. Draw a mark anywhere on the spoke (pictured in red) and measure the distance from it to the end of the spoke (dimension A). Then stick the spoke through the rim and screw a nipple on it, stopping somewhere around the point where spoke end reaches bottom of screwdriver slot in the nipple's head, or slightly below (that simulates initial position before the start of final tightening). Settle the nipple in its hole and measure the distance between your mark and inner rim surface (dimension B). The difference K=A-B is our length correction. Add it to the previously calculated length l and you're done. Or modify the calculation if you like: instead of using inner rim diameter D, use "effective diameter" D+2K, the result will be pretty much the same. Effective rim diameter (ERD) is a frequently used term and some manufacturers publish it for their rims, but I have already seen an incorrect one, so it's better to measure it ourselves to be sure.
The best is if the spoke ends somewhere between the top of nipple head and bottom of screwdriver slot when the wheel is finally tightened and trued. If it is a little longer and sticks out above the nipple, it can puncture the inner tube (only a concern with single wall rims), but we can file it down and save the day. If it is longer than that, the nipple hits end of thread before the spoke is fully tightened - there's no rescue from there, just take everything apart and go get shorter spokes. If a spoke is too short and doesn't reach above the rim bottom, there is a possibility of stripping a thread or tearing a nipple apart during use. Depends on the load.
The calculated length must be rounded to whole millimetres. Standard lengths (made cheaply in large series) are always even, custom lengths can be any, even or odd.
Holes in a rim are zigzag rather than in line:
Left side spokes go to the holes closer to left side of the rim and right spokes to right holes.
Holes in hub flanges are not mirrored, they are offset by half their pitch. It is clearly visible on this big hub:
The holes are closer together on smaller hubs, but their relative position is always the same. Stick first spoke from the outside through any hole, as on the picture above. Now we need to stop and think. The other end of the first spoke goes in a rim hole which:
Fill in the rest, skipping one hole on the hub and three on the rim:
A drop of oil on the threads makes screwing easier, especially with reused nipples.
Continue with the other side, inserting the spokes from the outside again. Start next to the very first spoke and also lean it away from the valve.
Continue inserting spokes, skipping one hole at the hub and three at the rim again (one of the three is already occupied, but don't let that confuse you). This is what you get:
Now turn the hub against the direction of normal wheel rotation, so that the temporary radial lacing transform to a proper tangential one. Why against the normal rotation? Because spokes from the half we have just installed are harder to replace (several others must be removed to get one out), so we want them to point in a direction that makes them loosen when force is applied to pedals. The other half is more stressed and fails more often (scores 4:0 on my bikes so far). Do the spokes next to valve hole lean away from it? Good, let's go on then.
Now the fun part begins. Insert another spoke into some hole, this time from the inside. Lift it to vertical position and turn agains the direction of the other spokes: over first, over second, under third, skip one hole after it and here we go:
For a double cross, the procedure is easier: over first, under second, skip one hole and screw a nipple. And even easier for single cross: over first, skip one hole and screw.
Crossing under the last spoke is not trivial, the new spoke needs to bend a little to clear the rim. Be careful, just flex it like a bow, don't bend it permanently! If you can't, temporarily unscrew the impeding spoke. A less tedious alternative - in theory - is to first stick all spokes at once into the hub, then aim and cross them when still loose, and finally screw them all into the rim. I don't know if it really works in practice, I never managed to do it that way.
Continue the same way around the whole wheel until first side is complete:
Now do the same on the other side. Stick a spoke from inside, cross over, under, skip a hole (occupied this time) and screw a nipple:
Continue until you run out of spokes, nipples and holes (ideally all three at the same time). Lacing is finished - easy, wasn't it?
Start by setting all nipples to some initial position, for example by aligning their end with the edge of spoke thread, bottom of screwdriver slot with spoke end, or something similar - do the same for all, the spokes should become slightly tight. This is the moment of truth - if we find the spoke ends sticking out through the nipples or barely holding by a few thread turns, we have no choice but to dismantle the wheel and go to a bike shop to exchange the spokes for longer or shorter ones (it's a good idea to measure by how much).
Now fix the wheel into its fork, in the exact position you want to have it at the end (of course, special truing jigs exist, but they are usually used only by professionals who don't need to read this tutorial). Theoretically the wheel shouldn't be so crooked that it wouldn't turn, so let's spin it, enjoy the taco shape and start tightening.
First tighten the nipples uniformly by the same amounts - one turn, half turn etc.. Check spoke tension after each run and try to keep it equal for all of them. You don't need a tensiometer, just pluck the spokes like guitar strings and tune the whole wheel to roughly the same note. Caution: driven wheels are often asymmetric due to wide sprocket clusters, so the right side needs to be tighter.
When the spokes stop rattling and wobbling, they are tight enough to start truing. Start by rough alignment in the axial direction (sideways, parallel with axis) because it's easier. How? Hold a suitable plastic or wooden object against the fork, shove it close to the rim, spin the wheel and see where it touches. Alternate tightening and loosening of spokes in the particular area to move the rim to one side. Feel the rim from both sides to avoid pushing it too far in one direction. Then align the radial direction (parallel with radius, perpendicular to axis). This is more difficult because the nipples need much more turning than for the axial direction. Tighten or loosen the nipples the same direction on both sides. Try to true the radial direction as fully as possible now, it would take much more work later.
Wobbling is roughly smoothed out, so tune the uniform tension again. It shouldn't untrue the rim by more than a millimetre or two. Now go find out what the tension should be; for starters, go and feel or pluck spokes of some existing decent quality bikes and compare with your new wheel. Then start the final tightening: every spoke by a quarter or half turn (all of them equally) and repeat until the tension gets where it should be. It must be big enough so that spokes between hub and ground stay reasonably tight even when we sit on the bike. While riding, every wheel turn means one load cycle for every spoke, from highest to lowest tension and back. Metal fatigues fastest if the lowest tension approaches zero (resp. if tension alternates with compression, but that doesn't happen to spokes). If the initial tension is higher, it paradoxically lives longer. In addition, a loose wheel is flexible, misbehaves in turns and its rim is more prone to denting or tacoing.
Now fix everything that remains: rim wobble (hopefully only axial now) and uniform spoke tension. If I remember correctly, maximum legal wobble is about 2 mm, but it's no problem to get under 1 with a new rim.
Finally, relieve all torque left in the spokes. Lay the wheel on a table or floor, axle end down, and push the rim down firmly by both hands. Most probably you will hear pings as the nipples settle. Push at several other places around the whole perimeter, flip the wheel over and repeat it on the other side too. Check for the last time if the rim still runs true, and you're done.