Logos should be vector (generally eps/pdf, svg, or a native .ai file) and not jpegs, bitmaps, pngs etc. They can be made transparent and printed on any background. If you must use colour, do so with care – colours change depending on reproduction and that wonderful shade of bronze you've selected on-screen turns out to be steaming turd brown on the 10,000 letterheads you've had printed. You should – if you have colour – have a black and white alternative. Consider whether you need an inverted version of each for printing on dark backgrounds. Convert any fonts in the final versions to paths (avoid rasterizing them). Ensure your logo is scalable, so print it small, and print it big and check everything remains in proportion, particularly lines and strokes. Also proof anything with the logo on it.
Most print shops these days offer design advice and consultancy. I wouldn't recommend tracing, a logo should be simple and quick to draw from scratch and will look tidier. Never try to be too clever with logos, they should be simple and professional.