First lesson in this: never design a logo just rasterized for a customer. You should be doing the designs in a program such as Illustrator or Freehand or Corel Draw in Vector first, and then go into photoshop if you need to add the pretty elements to it. The reason why is that anyone who prints a logo or does design or anything like that will require you to give them a vector logo.
I will so though, if you cannot give them a vector logo, atleast build it at a huge size in your program so it prints nice. Meaning a dpi such as 300-600 so the quality comes out ok, and a measurement of over five inches wide, so they have options in the future. But don't do that now, you've already built it and it's too late. If you make it bigger, you'll just make it blurry.
I'm not trying to slam you, so I'm sorry if I come off wrong, I don't mean to. I'm just telling you what's the standard.
Ok, programs? There are a couple, and some that can do it inside their program. If you have Flash, it will trace your bitmap into a vector file and you can export it as an eps. Photoshop will allow you to trace the image into vector 'paths' and export the paths as an illustrator file. A program called Adobe Streamline can trace and export at excellent quality.
However, Frank is right about the quality, and the best way to do it. Any program that traces a rasterized file will most likely do it VERY poorly, close, but poorly. Your best bet is to place the rasterized image in a vector program such as illustrator, etc. and redraw it. Only then will the quality be good enough to print.
Before you post, read our: 
