Selecting voltage rating for capacitors
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.