Inkscape is free and has an autotrace function. It's not perfect however, so you still may need to spend time editing. If its a very complex design, Adobe Illustrator's ImageTrace does a really good job and Adobe does offer a free trial.
Autotrace requires enough pixels to get good results. I think a good value is close to 3000 pixels in the longest dimension so for letter size art that works out to about 300 dpi. If the art is very detailed and or very small, a higher scanning dpi might be needed.
PNG is the best format to use in my opinion, unless one knows how to adjust the compression to give the highest quality when saving a PDF or JPG.