Obviously, the newspaper's production department should be the authority on how to prepare files for their output. In the absence of their advice, I'd say it should be just like any other 4-color job, with the added measures you'd typically take for color newsprint, where colors often get oversaturated and dot-gain is unforgiving.
Aside from that, I'm not sure why your graphics are embedded in the InDesign file, or why you'd be sending anything other than PDF.
The color profile for newsprint is radically different than for typical sheefed offset. Newsprint usually has a much lower total ink limit than normal printing, so converting an image with full tonality using the default Color Settings would produce blacks approaching 300% and the image would be unprintable on newsprint where the limit is usually between 220 and 260.
The US Newsprint SNAP 2007 profile that is included with CS has a ink limit of 220 which can produce significant color shifts when you make conversions, but its soft proof does show the effects of desaturated color, extra dot gain and brownish blacks that you get when printing on newsprint.
There's also the ECI newsprint profile, which has a total ink of 260
Gentlemen, thanks for your help. Very helpful information. I especially apreciate the ECI nesprint profile. BTW, what does ECI stand for?
European Color Initiative http://www.eci.org/en/start
The eci profile assumes less dot gain than SNAP.
Newsprint color is variable so you have to lower your expectations. A newsprint profile will give you correct ink limits if you use it to make conversions to CMYK (but won't for existing CMYK). Either SNAP or eci will do a better job soft proofing the weak blacks and desaturated color you will get on newsprint. When you color correct RGB in Photoshop turn on Proof Colors so you preview the smaller gamut.