Step 1: What You Need
-stencil materialI like to use very thin polycarbonate plastic. You can get large 2'X4' sheets for ~$2 from mcmaster.com
-stencil designI usually do either pure photoshop vector or image manipulation with the cutout filter
-projectorWe had one around the office for playing Halo on.. I mean... meetings.
-permanent markerAny kind will do, but Sharpie has my money.
-cutting knifeI like exactos. If you cut anything thicker than .004" polycarbonate, try getting the thicker-handled ones.
-fresh, sharp bladesCost: ~1.50USD. Benefit: Much, much easier on your hands.
-cutting matI don't really care that much about this- I only have this nice one because I rescued it from a dumpster. Cardboard will do in a pinch.
-tapeAnything will do, even tacks if you don't mind holes in your wall. I had cellophane tape handy.
Step 2: Design Stencil
For colors like this light blue, you can lose your mind trying to trace the untreated edge... or you can slap a 1-3px black stroke on those layers.
Step 3: Project Stencil Onto Wall
If you're concerned with scale, you can project a few elements with a defined scale, and adjust the projector until it fits.
I wasn't really concerned with that, and I don't think many people making stencils will be.. so I skipped it.
Step 4: Tape Up Material
Step 5: Trace Stencil
If you had to do this a lot, I'd suggest a setup with a large transparent glass table, and the projector below it. Tracing things while seated is much easier than doing it perpendicular to a gravity well.
Actually, that makes me think... I wonder what tracing something in zero gravity would be like? I think you might have to brace yourself of a bulkhead or something of the sort.... weird.
Anyways, you'll likely need to modify your design for contiguity- an island of material will fall right out of the stencil, you need to build it with little 'bridges' to connect it with the rest of the stencil- see the images to see what I mean.
A technique I like to use to double-check what I draw before I cut it out is to simply draw a little X on the bits I'll be cutting out, then stepping back and imagining them all falling out.
Step 6: Cut Stencil
Make sure to use the cutting mat, or you'll have your mom / significant other / whinydude on your case.