Like Kurt says, get all specs from the newspaper.
You will need to know about colour conversion from RGB to CMYK most likely using the paper's own profiles.
The people at the paper will most likely be able to send you what you need and they will assume you know how to use it.
In the meantime you must realize that most offset printed newspapers have a dot gain of 30% or more (while normal offset dot gain on good quality stock is in the range of say 15%).
To save ink they also use a lot of undercover removal in dark colours, so it is imperative that you know how to colour separate for the specific process.
This probably explains why you were disappointed with the results of what you thought were pretty pictures.
The colours came out all dark and gloomy because you didn't make allowances for the effect that poor quality paper has on printing ink.
The other thing to bear in mind about graphics for newsprint (as opposed to photographs) is that simple colour mixes using only 2 or 3 colours usually come out better than 4 colour mixes.
Colour percentages above about 80% will fill in, so you should try to choose colours that are either solid or in the low and mid % range, but first and foremost try to avoid difficult musty colours – they will become even more musty in print.
