As is customary with preparing images for print in a magazine or newspaper, I convert my digital photos from RGB to CMYK before inserting into my publishing application. However, when I'm printing photos at my local photo lab, I leave them in RGB. In fact, I once tried printing a CMYK image; the printed colours were completely off. In what way are the printing machines at the photo lab different from the traditional offset printers?
The lab photo printers are likely to be dye-sublimation, or silver-halide (where the digital image is projected onto normal photo paper) which unlike lithography don't require halftoning, however they still use ink and thus follow the subtractive colour model, so the principal is the same.
The reason your colours were off is probably due to CMYK conversion using a different colour model than the one the printer uses (Photoshop defualts to SWOP CMYK, which I believe was developed for an offset print process), as the dyes in a photo lab printer will be different in colour to the ones used in lithographic printer and so require different quantities of each colour in order to [try to] replicate a given RGB value.
Unless advised otherwise by the printers you're probably best using the widest gamut available to you (usually Adobe RGB, which will likely contain 99% if not all of the printer gamut) and let the printer handle the CMYK conversion. You can ask the printer for a colour profile for their equipment in order to have more control over this process and "soft proof" the expected results on your monitor. But unless you need to edit the image in CYMK (for example to get a specific black mix) doing the coversion yourself will just create much larger files (since you can't use jpeg for this) and runs the risk of incorrect results if done with the wrong profile.
At the end of the day producing artwork for a subtractive print process using an additive output device (i.e. a computer monitor) is error prone. It will take several attempts to get the colours how you want them when printing.
The vast majority of photo labs only know how to handle sRGB images. Many of the RA-4 based digital mini-labs don't recognize embedded profiles and just treat everything as sRGB.
There are new inkjet-based minilabs showing up in some locations now, but they're still catering to consumers printing direct from point-n-shoot jpeg's, so your best bet is still to stick with sRGB.
Some labs catering to "pros" (namely wedding/portrait photogs) might support Adobe RGB in addition to sRGB, but don't assume that's true; always ask first.
Even if you're using a lab that prints with inkjets, they're almost certainly using RGB-based drivers, so don't assume that just because the printer has subtractive inks that you should be handing them a CMYK file. Never give a photo lab CMYK images.
There are some fine-art printers and high-end service bureaus out there who have a fully color-managed workflow and can handle pretty much any embedded profile; but they are pretty rare (and expensive).
Well, if you are taking photos to a local lab you have to adapt to what they do. Some labs accept multiple color-spaces and others may just ignore the color-space in your photos which is why the colors look off when you get the print.
Regardless of what they accept you should ask about what they USE. Most labs always convert to a specific color space, regardless of what they accept. If you want the most reliable output then I suggest you convert to the color-space used by the lab. If you ask and they do not know, find another lab or submit sRGB which stacks the odds in your favor.