Illustrator CS & CS2 have a "Trace" feature.
Import a photo and it will do it's best to vectorize it. If you have access to a copy, you might want to give that a try.
You can do it by hand in photoshop, but it is a pain in the ass and takes a long time.
Basically for each line, area of solid color, etc. you make a selection. THen you convert that selection into a path. Once you have all of these paths made & edited (which can take forever) export the paths to illustrator, and you'll have a vector version.
Best way to to use Illustrator's Trace function though...
Brain21