Create Sharp Edges for Printouts

I'm new to graphics design with Photoshop but recently had to create a logo to put on various forms.

I've created it in the CMYK mode in both 600pdi and 72pdi. The logo consists of predominatnly texts and some shapes. I've applied the anti-aliasing filter and saved a copy each in the TIFF, JPEG, and GIF format. However, the printouts of all versions of the logo look pixelated at the edges. What can I do to create smooth edges on the printouts?

Any pointers will be greatly appreciated here. Thanks!