There are several possibilities:
1. You are sending them images in Adobe RGB space or ProPhoto RGB. Most mass-production consumer labs use software that does not read the embedded color space but rather simply assumes that every photo is in sRGB space. This speeds up their workflow and for the most part works well because most of what they receive is jpgs direct from simple cameras that output only sRGB. More expensive "pro" labs read the file's metadata and make the appropriate conversion if the photo is not sRGB.
2. Your monitor is not calibrated and therefore you really don't know if the colors it is showing you are what is really in the photo file.
3. Your monitor is too bright. Most monitors come from the factory set with their brightness and contrast all the way up; great for gaming, but not good for print preparation because paper prints can't produce the same levels.
The first (and easiest) thing to check is #1.
Good info from Elie.
If you have not calibrated your monitor, and you want to check the brightness, go here
and check the A-Z gray scale just above the Amazon price list.
Adjust the contrast to see the difference between A and B whites.
Adjust the brightness to see the difference between Y and Z blacks.