Step 4: Choose your Weapon
One thing to consider is that thinner materials make for easier stencils to spray. This is because you don't have to spray from a perfect 90-degree angle to the work, which you have to do with thicker materials, otherwise the surface of the material will block the paint at the edges. This results in "fuzzy" edges.
Another option is a material called frisket film. Frisket film is a material widely used for stenciling by airbrush artists, especially in the automotive industry. It is a plastic film that is a bit stretchy and is adhesive on one side. It cuts very easily with an X-Acto and can be bent around curves. If you're working on a very smooth surface (i.e. finished metal, fiberglass or plastic) frisket film is second to none. It can work well on wood and painted walls, too. It won't really stick to anything rough, like brick or stone. The major problem with frisket film is that it is very flexible and tends to stick to itself (imagine a stencil made from scotch tape). This makes is virtually worthless for more intricate stencils. It's also very, very difficult to get multiple uses out of it. The adhesive will work more then once, but peeling anything but the simplest design off without stretching it or sticking it to itself is quite a challenge. Frisket film can be purchased at art supply stores and some automotive places.
If you're using cardboard, foamcore, etc you'll need to glue your paper guide down so it doesn't move while you cut. I suggest Spraymount for this, which is a spray-on adhesive that you can buy in art supply stores. Any spray glue will work, though. Just make sure you don't use anything that will harden beneath the paper and make it hard to cut, or will remain gooey and stick to the blade, like rubber cement.