Why does it seem that the potential difference dependence of capacitance and total energy stored in a parallel-plate capacitor are contradictory? Consider a parallel-plate capacitor.  Charge is stored physically on electrodes ("plates") which are flat and parallel to one another.  If one electrode has charge $+Q$ and the other electrode has charge $-Q$, and $V$ is the potential difference between the electrodes, then the capacitance $C$ is $$C = \frac{Q}{V}$$
(This definition of $C$ is given in, for example, Introduction to Electrodynamics by David J. Griffiths.)
But, now, let's think about the energy stored in the electric field between the electrodes of this parallel-plate capacitor.  As stated in Griffiths on page 105, "How much work $W$ does it take to charge the capacitor up to a final amount $Q$?"  It turns out that $W$ is $$W = \frac{1}{2} CV^2$$
So:
(i) the capacitor's capacitance $C$ goes like $\frac{1}{V}$; and 
(ii) the energy $W$ stored in the electric field goes like $V^2$.  
Are statements (i) and (ii) at odds with one another?  I am sure that they cannot be. But conceptually I am having difficulty.
We desire high capacitance -- we want to put as much charge on the electrodes as possible, because if we accomplish this, then I think that will increase the energy density of the system.  But is what I just said true?
If we manage to increase $Q$, then by $V = \frac{Q}{C}$, the potential difference $V$ between the plates will also increase.  This, I think, is why capacitor electrodes are separated by a material (such as a polarizable dielectric material like a slab of plastic); otherwise $V$ will become too large and the breakdown voltage will be reached, generating a spark.
But, now, the equation $W = \frac{1}{2} CV^2$ (where I think that $W$ can be conceptualized as the energy stored in the electric field between the electrodes) seems to say that as $V$ increases, so does the energy $W$, quadratically.
So, my question is, do we want a capacitor to have a large potential difference $V$ or a small potential difference $V$?  If $V$ is large, then $W$ is large (which we want), but $C$ is small (which we do not want).
Am I somehow thinking of two different potential differences $V$ and confusing them?
 A: First of: the energy W does not increase exponentially it increases quadratic!
Second:
What do you want? 
Energy density!
So to get good high energy density you need high C because you can (as you already stated) only go to a certain amount of voltage until you get a breakdown. The problem is, C does not change easily. If you take a simple Plate - Plate capacitor 
$C \propto \frac{A}{d}$ where A is the Area of the plates and d the distance between them. The smaller the distance the higher the electric field gets between the plates gets relative to Voltage ($|\vec E| \propto \frac{U}{d}$) the faster you get a spark. So the only thing you can actually increase safely is the area. That of course increases the wight/size of you capacitor, reducing the Energy density. This generally applies to all capacitors
Wikipedia does have an excellent article about capacitors:
http://en.wikipedia.org/wiki/Capacitor
Third:
About the capacitance:
A spring is a very good analog to your problem:
A newtonian spring has a certain flexibility, describing the force you have to pull it relative to the expansion of the spring:
$F=k \times x$
Where F is the Force k is the flexibility and x the way. So the capacitance is actually k in this analog. But F is not the Energy W. 
$E = \int_0 ^x F(x) dx$
So the more you pull the harder it gets to pull because the force from the spring increases. So to get the energy you can not just calculate $E = F \times x$ but you rather have to integrate the way.
That of course gets you to 
$E = \frac{1}{2} k x^2$ 
Back to the Capacitor:
The more electrons you put in it, the stronger becomes the electric field between the plates of the capacitor. So you have to increase the voltage. The capacitance just tells you how high your voltage has to be (how hard you have to push) to put more electrons on the plate.
A: Capacitance depends on the geometry of the conductors holding the charge. To maximise the energy stored, you maximise the capacitance by changing the geometry of the conductors, and maximise V by transferring as much charge as possible.
A: 
So, my question is, do we want a capacitor to have a large potential
  difference V or a small potential difference V

No, this is not a good question, I'm afraid because, in general, we don't think about capacitors this way.  Generally speaking, the important parameter is the value of the capacitance and this value is determined by various design equations.  We want the capacitor to have a particular value of capacitance which may be very small, very large or anywhere in-between.
Now, in the limited context of energy storage applications, e.g., the reservoir capacitors in large audio power amplifiers, then we simply want large capacitance.  The energy stored in the capacitors feeds the amplifier most of the time; the capacitors are rapidly charged on the AC peaks.  The voltage across these capacitors is set by the AC power transformer and rectifier.  We simply need to make sure that the capacitors we use are rated for that voltage or higher.
A: As a summary of what other answers have already stated, in essence:


*

*Capacitance is a function of the geometry of the capacitor (directly proportional to the overlap area of the plates and inversely proportional to it's separation) and of the relative permittivity of the dielectric employed. Once this constructive parameters have been fixed, it's capacitance gets uniquely defined, and so it's constant when the capacitor gets charged and discharged (assuming linear response, as it's the norm in standard circuits).

*The relation between voltage between the plates of the capacitor, the accumulated charge and it's capacitance is just the definition of the latter. That capacitance is a property of the system which is a function only of geometry and dielectric's permittivity, is a fact that can be deduced from this definition.

*So, once you have picked up a capacitance (by fixing the parameters involved as explained above) maximization of stored energy in the electric field generated gets down to increasing voltage between the plates as much as possible. Nevertheless, increasing the electric field's strenght has a limit (the dieletric strength), which corresponds to the breakdown voltage of the dielectric, so that is the maximum voltage safely and technically attainable. So:


$W_{max}=\displaystyle\frac{1}{2}CV^{2}_{max}\ ;\\V_{max}=E_{max}\cdot d\ ;\\ C=\displaystyle\varepsilon_{0}\varepsilon_{r}\frac{A}{d}\Longrightarrow W_{max}=\displaystyle\frac{1}{2}\varepsilon_{0}\varepsilon_{r}E_{max}^{2}\cdot A\cdot d=\displaystyle\frac{1}{2}\varepsilon_{0}\varepsilon_{r}E_{max}^{2}\cdot Vol_{\ dielectric}$
Corollary:


*

*The amount of energy stored in a fully charged capacitor is just obliquely related to it's capacitance. Nevertheless, even though the energy of the electric field is directly proportional to the volume of dielectric between the plates (the product of the plate's area and their separation), for a given amount of dielectric material, the preferred geometry implies a large area and as little separation as possible, because that arrangement allows more compact designs. That's why a larger capacitances leads to larger energy densities in practical applications.

