As briefly described before I chose 1/32" rubber sheeting for its flexible nature and its non slip properties, not to mention it is easy to cut and easy to clean.
I am not going to go over how to create a stencil because others before me have covered it quite well, so if your new to stenciling then check here: Creating Complex Spraypaint Stencils by Hand
and if your new to laser cutting check out any number of fun projects that cut tons of different materials here: Laser Cutter.
I will say this however you will need to do tests probably varying the speed of the laser the power level, and the ppi(pulses per inch) to find a good setting that will cut through the rubber without melting it too much. Also you can format your stencil in Photoshop, Illustrator, or even Flash. Just make sure that your strokes are hairline and that there are no fills when you export it as an EPS file if your using a laser cutter. Again the links above have good information about making stencils, the only thing you have to remember is that you will be dragging your applicator across your stencil so becareful not to make alot of thin lines that could break or move during application. So now lets look at a different material to use with our stencil.