Why not post an image of the logo so we can see what you're working on? I can still offer a general answer, however:
If you use an image (anything raster, including JPG, GIF, PNG, BMP, TGA, etc.), you have pixels, period. Raster images are grids of pixels, thus if you enlarge a raster image very big, it will look pixelated (or just extremely blurry, depending on the method used). There is no program that can magically correct a pixelated image.
There is one and only one way to completely avoid this, and that is to use vector drawings only. If the "image" you have a raster version of is in fact something that is essentially a drawing (think sharp lines, simple (if any) gradients, that sort of thing), and you can faithfully reproduce it from scratch in Illustrator using the tools available (the image trace can be helpful, if used appropriately and judiciously), then that is your best option.
However, if your "image" is something that is based from a photograph, painting, or other such image that has a lot of subtle complexity, then you are better off leaving it as a raster image. That's what raster images are for. In that case, obtain the highest resolution copy of that image that you possibly can. If the logo will be printed, look for at least a 300dpi version of the image, at the largest size it will be printed.(1) However, talk to your print shop for their preferred raster image resolution.
Note that you absolutely must not simply take your existing image and resize it to obtain the desired dimension; that's the whole problem you're trying to avoid. You need an original source image from a camera, scanner, 3D render, etc., at the exact dimension you want to print at.
If you are not printing, and the logo will only display on screen, you can get away with a much lower resolution, in the 100-120 dpi range, but there it's even more important to avoid resizing, due to the large, sharp, square pixels on screen.
- E.g., if it will be printed at 2x2 inches, then you need a 600x600px version minimum. If you need to print it on a 10 x 10 foot billboard, go for at least 35000x35000px! (Although at billboard distances, you can often get away with less.)