Yes, if the printers just say CMYK and no further details given you should let them do the conversion. There are so many different CMYK settings and you have to know the exact one that the printers will be using. Looking at the CMYK choice in Photoshop's Colour Settings window will show how many choices are available, and these will vary based on where you bought the Photoshop! On my machine for example I have the American and Japanese CMYKs because I bought my upgrade to CS5 from Amazon in the USA, so I have no european pre-press settings available.
I didn't mean to say that converting to CMYK should be done routinely, just that if you are using Photoshop and you get a gamut warning try the conversion. It will automatically convert the out of gamut colour to the nearest in-gamut colour, and this may not even be noticeable on the screen whilst the print will have only in-gamut colours.