PGO
Are you thinking about doing more print work in the future? Or is this a one off? Indesign isn't cheap and really you could do all your design work in illustrator (if you have that?) If you are going to do more print work I would definitely consider getting a page layout software like Quark or Indesign.
Your artwork in this case should be made using vectors. I would then add text (address name etc) using a pagelayout tool like indesign - although you could use illustrator.
Do you have access to pantone refs? Ideally you want to colour match with simething physical so you know what your going to get. The differences between your screen and the printed article will be always be noticable.
Demand your printer provide you colour proofs before they go to print so you can see if there is any errors.
As for file types, well your printer should be able to accept most types. PDF (as mentioned) is the way to go, but they will happily take EPS or a Quark doc + images (lock your page if you provide it this way)