The RAW ICC is not embedded, it's converted.
You need to convert the final photo to either sRGB or AdobeRGB (ask them what they need) profile before saving it.
In Photoshop 6 it's the menu item MODE/CONVERT TO PROFILE/
NOTE: Many printing firms offer an ICC profile for their printer, which gives you a possibility to adjust the photo at home. This gives very accurate results.
If you get their own printer ICC profile:
1. Install the profile
2. Edit the photo (convert RAW to TIFF, sharpen, if you used RAW ICC you have to convert after that to your working color space, usually sRGB)
3. When you're finished editing make a duplicate and CONVERT that duplicate photo to their printer ICC profile.
4. At this point the duplicate photo will probably look a bit wrong. It just contains corrected data for their printer, the final print will look like you saw it in original photo (the one you duplicated).
5. Now, save the image WITHOUT any color profile (untick ICC profile selection in save dialog) as either JPEG or TIFF.
6. Send the image to print company.
(These steps were for Photoshop 6)