Adobe Gamma only helps you to get a full range of tones and to get middle grey middle grey, which helps you maintain your calibrated workflow at the viewing stage. It's based on your visual estimation so is not fully accurate, but is good enough for 99% of the uses. It does not in any way affect your pictures, aside from how you view them.
ICC profiles on the other hand are calibrated colour profiles so that colours appear similar. Usually this involves calibration in several stages. A image can be imported with a certain profile, converted, viewed and printed. To get the colour to match between you and your lab, you need to pick an ICC profile, do your editing in that profile with your calibrated monitor, save the picture with the profile enabled (tick the box in Photoshop). Then, your lab needs to know what profiles you saved in. If they open the file in Photoshop printing then you're safe because they will be warned that a different profile is embedded if one is indeed embedded. If they don't, then it's possible they may print using a different calibration profile and discard the original profile.
If they print with the same profile, then it will appear effectively identical to any other output device with that profile, including calibrated monitors and printers.
