>and scanned it into my computer as a pdf file

The .pdf format is widely accepted, but it sounds to me like you've just embedded a raster file into the document - that is to say, it's a scanned image (a bitmap, or a jpeg) as opposed to actual vector information which describes the shape numerically - this is what the 'tracing' stage is all about - converting the picture into a vector... I doubt very much that your scanning software has converted said scan into vectors for you... You'll effectively be sending the shop a pretty picture with no useful information for them to base the cutting on.

My suggestion would be to import your scanned image into an application (such as inkscape or illustrator) and use that to trace the lines and curves that make up your design, then get rid of the image from the canvas and save the resulting line-work as a .pdf

Inkscape is open source and easy enough to get to grips with.

Wal,