Photoshop :: Printing Magazine, CMYK Issues

I've been using Photoshop

This is my problem:
I'm trying to publish a magazine for my community, and I'm using Photoshop CS3 to design the magazine. From what I know about printers and printing presses, they print using CMYK - therefore when I create my documents I've been using the CMYK 8 bit Color Mode. My resolution is set at the 300 pixels/inch, but I'm not sure what my Color Profie/Pixel Aspect Ratio should be.

I've also been told that most printing companies prefer PDF documents, and I don't know the right options to choose when saving my PSD's as PDF's through Photoshop.

I noticed my first problem when printing a sample at Kinko's. I had mostly black and white on my image, but I had a light yellow to dark yellow gradient as a background, and when it printed, banding appeared towards the lower part of the page where it should have been dark yellow. Basically that gradient wasn't smooth. I also noticed this on my computer when using a CMYK Color Mode, but it was less subtle (when I use RGB, the gradients are perfectly smooth from light to dark).

The sample I took to Kinko's was a:
Flattened image,
Then saved as a Photoshop PDF
As a Copy
ICC Profile: U.S. Web Coated (SWOP) v2

I just need to know the right options to start my image, and the right options to save my image as a PDF to ensure the best print quality with no sacrifce to color, gradients, etc.