Mbriant's got it.... Calibration is the key! Monitors are very unstable devices and (depending on the monitor) can vary tremendously in their color/brightness over the space of a few months. Furthermore, they aren't even calibrated to a set standard after manufacturing. Thus what you print may have little to do with what you see on the monitor (or what is in the actual file).
Printing is similarly complex because it is, generally, an inexact science. Not all printers replicate a certain RGB value in the exact same way that another printer would. Another problem is that, in some cases, a monitor can replicate more contrast than your printer can.
Since you are using a service, there is an added layer of potential "correction" that they do in house... Though with digital they generally do much less of this than is done with film.
What to do? First things first, calibrate your monitor. There are non-hardware tools that can do this (Photoshop comes with one) but they are rather error prone. (Or at least they are when I use them!) Hardware color calibration is much more accurate and fairly cheap these days ($89 for the cheapest Spyder). So long as your monitor is up to the task (accurate production requires a certain level of brightness etc. but most monitors can handle it easily) you're all set on the digital end.
Printing is a bit more complex because you are using a service. Ideally you want your printer to be calibrated to your monitor... either by eye using color swatches or using a hardware system... But this is impossible if you are using a service.
Luckily, many services have at least rudimentary calibration information for you... Dig around their website for information on this.
Realistically, however, your monitor is far more likely to be far out of proper calibration than their printers are... so start there and it may solve your problem!