Make full-color stencil art using a laser cutter. Ideal for large-scale printing on various surfaces.

Buy the stencils on Etsy.

Step 1: Materials

Tools

Laser cutter: you could make one for $50, but I had one available.
Image processing and plotting software: I used Adobe products and AutoCad, but there are certainly other options.
Face mask for respiratory protection

Materials

Tape: masking tape or painter's tape. The wider the better.
Stencil material: I used chipboard; transparencies should work as well.
Spraypaint: I used Krylon indoor/outdoor gloss spraypaint, about $3-4 per can at Walmart (I used Black, Raspberry, Global Blue, and Bright Idea).

Step 2: Choose and Separate an Image

Select a subject. I went with Andre the Giant because he's fairly well known from Shepard Fairey's stencil work.

Resize your image:

Open the image in Photoshop.
Image > Image Size
I set "document size" to 800% width/height, at 300 ppi, giving me about 7x9 inches

Then we need to convert it to CMYK, normalize it and brighten it a bit so that when we halftone the circles don't intersect:

Image > Mode > CMYK
If it asks about Flattening, click "Flatten"
Normalize using Image > Adjustments > Auto Level, or do it by hand (recommended)
Open Image > Adjustments > Levels and in the minimum output level box enter 128 (this will, effectively, make the image brighter)

Separate the four color channels:

Select the "Channels" window (next to "Layers", or select from the "Window" toolbar)
Make only the "Cyan" channel visible
Select all
On the "Layers" window, create a new Layer and paste the channel
You should now see just the Cyan channel in black and white, save this as a jpg
Do likewise with the three other channels (Magenta, Yellow, and Black)

When you're done, you should have four separate black and white images, one for each channel.

There is probably a faster way to do the separation, or to do it in Illustrator directly. If you know, share the technique in the comments!

Step 3: Trace

We'll do the halftoning and vectorization in Illustrator.

Open up the cyan jpg in Illustrator.
Select the image
Edit > Edit Colors > Convert to Grayscale
Filter > Pixelate > Halftone. I chose a 30 px halftone size.
In the Control Panel, click the drop down arrow next to "Live Trace" and select "Tracing Options"
I used: Black and White, Threshold 128, 0 px Blur, Fills, 2 px Path Fitting, 100 px Minimum Area (so the tiniest halftone holes are ignored), Corner Angle 20, Ignore White. Save these options, since you'll need them three more times.
In the Control Panel select the "Expand" button, which will make paths from the Live Trace.
If you want to, clean up extraneous dots with the Direct Selection Tool (white arrow). If you select some dots to remove, and then hit delete, it only deletes the points you selected. If you hit delete again, it removes the entireobjects you are on the boundary of selecting.
File > Export. Select "AutoCad Drawing (.DWG)" For this window, my options were: Version 2000/LT2000, 1 inch = 1 unit, 8 colors, PNG raster file format, Preserve Appearance

If you're stuck, here's a similar walkthrough describing halftoning in Illustrator.

Step 4: Cut

Open the .DWG file in Autocad
You might have to Select All and hit "Explode" depending on what version of Illustrator and what version of Autocad you're using
Select the appropriate line weight and color (in my case, 0" and Cyan)
Send to the laser cutter, making sure that the color you've selected corresponds to the proper settings for cutting the material you've chosen.

Repeat the last two steps for the Magenta, Yellow and Black jpgs. The only difference between them will be in the halftoning step: when you halftone, you need to change the angle of Channel 1. For Cyan, 108, Magenta, 162, Yellow, 90, and Black 45; otherwise the four halftones will line up and overlap.

Instead of doing the four colors separately, I did all the Illustrator work in one step so I could make sure they were aligned. I added a rectangle around the perimeter that would help me align them when spraying. Another alternative: try adding four small dots near the corners.

Step 5: Spray It

Select a location where you'd like to share your work/play. In spraying the layers, I started with the densest (Yellow) and worked up to the least dense (Black). This seemed to work well, but I'm sure there are other techniques.

Place your first layer, tape it down, and mark the corners so you can align the following layers. I used lots of tape, but this is my first stencil so I still got some overspray. The can recommends a distance of 6-8 inches, which worked pretty well for me. I used about two quick coats per layer. Between layers I needed about 3 minutes for it to dry.

Step 6: Notes and Variations

There are a lot of directions you can go as far as reproducing full-color images with only four colors. Try other effects out besides halftoning, and see what you end up with. This idea was originally inspired by some magnificent stencil graffiti I saw in Rome: a detailed line-art portrait of a woman.

If you don't have a laser cutter, and can't build one, it is possible to print out the halftoned images and cut by hand. See Sten and Lex, The Wooster Collective, Bonard's MLK, ctrl84, RatherNotSay and AlexLionheart. They tend to use squares instead of circles for the halftone, which makes it a lot easier to cut by hand.

The thinner the material for your four layers is, the easier it will be to get paint in the holes. If you cut overhead projector film (normally polyester) instead of chipboard, there's the added advantage of washability. Even though with the chipboard I didn't have any issues with the paint gooping up the tiny holes.

T-shirts? I haven't tried, but have a feeling there'd be a lot of bleed.

With a thin enough material, you might be able to paint over the layers instead of spraypainting.

I initially imagined this as a cheap way to do larger-scale full-color printing on various surfaces. So long as you have access to a laser cutter, that's still a reasonable idea. If you can't get the laser parts for the DIY laser cutter, you could try making a machine that just prints stencils using some kind of vinyl/plastic/polyester and a soldering iron to burn the holes. (Purely speculative, watch out for fumes.)

Thanks to Bart Woodstrup for helping me with the Illustrator exporting and laser cutting.