In general, the voltage rating of a capacitor is the maximum it can take and still stay within specs. Unpolarized caps, like ceramics, can take any voltage +- the voltage spec value. Polarized caps, like electrolytics and tantalum, can take any voltage from 0 to the voltage spec value.
That said, different things happen to different cap types as their voltage gets near the maximum. With electrolytics, the lifetime goes down. In theory with a reputable manufacturer, the rated lifetime is at max voltage and temperature unless stated otherwise. You could therefore say the lifetime goes up if you operate the cap below its rated max voltage. The two major stressers of electrolytic caps are voltage and temperature. Large currents can also hurt them, but this is due to heating so is really a temperature issue.
Ceramics have different properties. Voltage doesn't effect lifetime of SMD multilayer caps much, assuming of course you don't exceed specs. Some ceramics however do not linearly store charge as a function of applied E field. They hold less additional charge for the same voltage increment at high voltage than at low voltage. This means the apparent capacitance goes down with voltage. The cheap ceramics, particularly those with "Y" in their names and a few others exhibit this effect more strongly than others. If you are just bypassing a digital chip, this doesn't matter much. If however the cap is used in a analog filter, then this probably matters and you generally want to stick to ceramics with "X" in their name and look over the datasheet carefully.
There are issues with too low a voltage too, especially with electrolytics. They work on a thin oxide layer on the alumimum. This can get degraded when there is no charge accross it.
So to finally give you a concrete answer, if you are going to use electrolytic caps try to aim at running them around 3/4 or 2/3 of their rated voltage. It's OK to have occasional spikes up to the maximum, but don't ever exceed it. It's OK for them to be off too, but it's better that they're not completely discharged for years on end.
You can put capacitors in series, but that rarely works out better than getting the right cap in the first place. As Steven said, two of the same caps in series have double the voltage rating but half the capacitance.
You also have to be careful that the DC level of the node between the caps is at about 1/2 the voltage. If one cap has a little more leakage than the other, and this is quite possible, then the mid node won't be near 1/2 way and the voltage rating of one of the caps is exceeded anyway. One way to deal with this is to put deliberate leakage around each cap that is significantly larger than their actual leakage. In other words, put a resistor accross each cap. Make these resistors has high as possible but to still have several times the cap leakage current flowing thru them. The resistors form a voltage divider that keeps the midpoint at about 1/2 the voltage.
However, all this is a kludge around your original problem. You want to power something at 5V and you have only a noisy 5V supply available. Putting a big fat 1 mF cap accross this supply apparently attenuates the noise enough, but there are other ways too. How much current do the noise-sensitive parts of your circuit draw? If it's limited to 100 or even 200 mA, then a ferrite "chip inductor" in series with the supply followed by a 20 µF ceramic cap to ground might by all you need.
Probably a all around better approach is to locally make your own 5V from the higher voltage the Arduino also uses for that purpose. I don't know what voltage the Arduino runs on, but somewhere in your system there must be a higher voltage with some sort of regulator making the 5V the Arduino uses. That gives you more headroom to drop a little voltage in a filter before your regulator. The filter removes high frequencies from the higher voltage, and the active electronics in the regulator then deals with the remaining low frequencies. That should produce a nice clean 5V independent of the Arduino and therefore with none of the Arduino's noise on it. Another advantage of this is that it doesn't load the Arduino's 5V supply. I don't know how much extra current capacity that supply has, but probably not a large amount.
Best Answer
This way, you halves the capacitance, doubles the power rating, internal resistance and lead inductance. As long as your selection of the cap has some reasonable margin, it should be good to go.