Definitely start with a small run first to gauge the market! Perhaps 10 copies of each design.
Know if you're doing bleeds or not as that usually costs slightly more.
Do ask for test prints so you know how the colors come out looking. Then you can adjust a 'for print' copy of your artwork on the computer to try and match the colors as you intend them to be. But in general you may need to lighten your artwork and adjust the contrast as most printers I've come across like to print darker than what is displayed on-screen.
Personally I can get by with using the local fedex kinko's with their cc2 paper. It's almost a cardstock so it's nice and thick and I sell 8.5 x 11 prints for $5 to $7 dollars.