Use vectors.
It is a lot more of a learning curve, but well worth it.
Not all of the programs floating around will handle vector art. Painter, for instance, is designed around replicating natural media and is all about working in bitmap. Illustrator, on the flip side, is normalized towards vector although it increasingly has a lot of paint-like functions as well.
Here's why this matters; a vector trace is inherently and infinitely scale-able. You can create it at whatever size is convenient, then change it to print or otherwise use at whatever scale is necessary for the prop.
And vector is transportable to CNC processes; to laser cutting and to CNC machining and (with a couple additional steps) 3d printing.
Last suggestion; if you don't already have a graphics program you own/are familiar with, get Inkscape. It is free, multiplatform, and does almost everything. The downside is a not always intuitive interface. (Originally I said Gimp, but Gimp is more a general art program and the vectors are more primitive. Inkscape, in my humble opinion, handles basic vector stuff cleaner and simpler than the recent bloated versions of Illustrator. My Holocrons are all done in Inkscape.)
