Hi Ainoko,
Can you tell us a little more about your situation? The big question is - who is responsible for converting your photos to CMYK?
The gamut of newsprint CMYK is very small, and most photographers die a thousand deaths when they either
(a) do the conversion themselves, and watch their bright colours flatten; or
(b) submit their photos for someone else to convert, and then see the awful print in the newspaper.
If you are submitting the photos in RGB format, then this is what you should do:
1. Shoot sRGB. Newsprint can't even encompass the sRGB gamut, so don't even contemplate dabbling in Adobe RGB.
2. Soft-proof using the SWOP Newsprint profile in Photoshop. It almost certainly won't be accurate for your newspaper, but it's better than nothing. It'll give you an idea of what colours are too bright to be reproduced. Then you need to desaturate those areas slightly to bring them into gamut. Under no circumstances should you go out of your way to "add extra contrast and colour" - that way lies disaster.
3. Enquire with the people who are going to be converting your photos, and try to ascertain if they know anything at all about profiles. If they don't, try to gently explain to them that the SWOP Coated profile that's loaded in their Photoshop or Distiller isn't suitable for their newspaper.
4. Cross your fingers.
If you are converting to CMYK yourself:
1) As above
2) As above
3) Ask the newspaper if they can give you an accurate profile. They won't be able to, but you're obliged to ask anyway.
4) Convert to CMYK using that SWOP Newsprint profile. Like I said, it's better than nothing.
5) Send the files, and make sure they are aware that you've already converted them! You don't want them attempting a clumsy second conversion.
Oh, and one more thing. When sharpening, go nuts! Newsprint is such a soft medium, you need to sharpen like crazy to get anywhere. I recommend USM 300,1,5 as a starting point.