Vector tracing is a way to convert raster files into vector images. See "Raster versus Vector artwork" why many people prefer vector images for their arcade art. Tracing can be very time consuming and labour intensive but at the same time it can produce stunning results.
The art of tracing
Tracing an image is quite similar to copying an printed image by overlaying it with a piece of transparent paper. The artist can then draw onto the transparent piece of paper and trace the shapes from the original. Vector tracing is based on the same principle but in a digital form. While the trace on the transparent paper is of equal size to the original, the digital version can be manipulated and reproduced as often and in any size as you wish!
The original artwork is loaded on a seperate layer in the art-software, the vector artist draws the shapes on top of it in a new layer. While it seems easy, tracing requires skill. Besides the fact that the vector artist needs to know how to use the software, a keen eye for colours and recognising basic shapes is needed for a succesful trace. A skilled artist can turn a blurry bitmap into a sharp clean vector image.
Auto trace tools
"Labour intensive? Time consuming? Why can't a computer do this!", I hear you ask. Well, it's a very good question. First, there are tools that can trace images for you. These tools produce various results, ranging from crap to slightly usable. The main reason is this: context. Humans can make out what a shape is supposed to be even if it is abstract or fuzzy. A few white, blue and black blotches can look like an eye for humans because the context (a face) is there. A computer will still interpret those blotches, well, as blotches. The vectors it produces will be more or less accurate renditions of blotches and will remain so as the vectors are enlarged. A human artist can make these blotches into a vectorised image of an eye.
The best autotraced vectors are produced if the sourcematerial is either high contrast and low details, or of very high resolution with distinct areas of colours.
A short list of trace software:
See also Raster to vector Wikipedia article.
Left - high resolution bitmap source
Middle - autotraced version, high settings via Vectormagic
Right - Traced by hand
As you can see, even with a high resolution image the automatic trace function isn't able to produce a well defined result.