What is the lowest capacitor voltage rating that is safe to use?
Be super careful about your capacitor's specifications. They might not be what they claim to be.
One problem with ceramic caps is that they lose capacitance as the voltage increases. For example, this X5R ceramic cap from Venkel is rated at 10 uF and 6.3V. The problem is that at 6.3V, the actual capacitance goes down to only 2 uF! That's an 80% drop! Even at 2.0V, you are missing 30% of the rated value.
This is documented here, but it is in no way limited to Venkel. X7R, X5R, and probably other ceramic capacitors suffer from this to some extent. COG/NPO does not seem to have this issue. I should point out that this problem was not listed in the overall capacitor datasheet, but only in a supplemental "technical data" document that was not located in the same place on their web page.
Your basic question, however, is "how much should I derate" capacitors. Of course if you ask 10 EE's about this then you will probably get 15 different answers. Here is my very rough rules of thumb or guidelines.
Aluminum electrolytic capacitors will be derated to at least 50% if the capacitance is critical. Meaning, I will use a 25V cap on a 12.5V rail. If the capacitance is not critical then I will allow for less voltage margin.
Tantalum capacitors will be derated to at least 50% on most rails, reguardless of use.
Ceramic capacitors above 10V will be derated to 50%. As the voltage drops below 10V, I will allow for less margin. I will run a 4.6V cap on a 3.3V rail, for example. But keep in mind what I've already said about ceramic capacitors.
The lighter the stress on a capacitor the less margin I will allow. For example, if a signal only very occasionally goes to 90V but is mostly below 50V then I might use a 100V ceramic capacitor. Temperature, voltage, current, and ESL/ESR effects all play into this. A capacitor with lots of stress will get much more of a margin.
Derating less than 50% only happens if there are other reasons to do so. If cost, size, and other factors do not come into play then I always derate at least 50%.
If a circuit is well behaved and issues of voltage spikes or other bad behavior is not an issue then I might leave less margin.
But these are only rough rules of thumb. You have to consider each case separately and weight the pros and cons.
Update:
Here is some documentation from AVX. It is on page 3, under the heading of "DC Bias Dependency". Note that their voltage vs capacitance curves for X7R are much "nicer" than what Venkel has-- so if the capacitor value is really important then do the research and get the capacitor that you intended.
Using tantalum caps for decoupling is silly with today's options. 1 µF 6 V ceramic caps in 0603 package are cheap and readily available. That would be better than 10 µF for decoupling anyway. A 10 µF at the power supply connection points makes sense, but not for decoupling. Take a look at the impedance plots of 100 nF, 1 µF, and 10 µF ceramic caps in the datasheets of any of the reputable manufacturers.
In additon to Olin's comments re size - note well that a Tantalum capacitor on a circuit with any sort of "power" present is a total disaster waiting to happen.
Tantalum capacitors are EXCEEDINGLY prone to insulation layer punch through at voltages only slightly in excess of rated voltage, and they are NOT self healing. Once the layer is breached the capacitor will dump available energy and self destruct. Normal failure mode is a hard metallic short. Optional along the way are smoke, smell, flame , sound and explosion. I have seen heard and smelt all these in a single exciting event on one occasion.
A very very short voltage spike on a power rail which exceeds voltage rating can puncture the insulation layer and then allow the power rail energy to finish the task.
Ceramic: Note that temperature effect varies with grade. Also mechanical microphony is worse on wide temperatre variation grades. Not usually an issue for power decoupling.
A low grade ceramic (poor temperature tolerance, so also poor mechanically) at the input to a regulator can "ring" when a step voltage is applied (such as at power turn on) and can destroy the regulator. This is unusual and easily guarded against but needs to be known about.
If ceramic does not meet your needs for some reason look at solid Aluminum capacitors (ie not Al electrolytic). They are competitive with Tantalum in capability size and cost but do not have Tantalums fatal failure mode.