In most capacitors (including the simple parallel plate capacitor, which is the one you refer to), changing the applied voltage simply results in more charge being accumulated on the capacitor plates, and has no effect on the capacitance.
A capacitor is nothing more than two conductors which are separated from each other by a dielectric material of some kind. When a voltage is applied across a capacitor, a certain amount of charge builds up on the two conductors. The amount of charge which accumulates is a function of the voltage applied - $Q=Q(V)$. The capacitance is then defined by $C = \frac{Q}{V}$.
Under most conditions, the capacitance ends up being purely a function of geometry. In the case of the parallel plate capacitor, one finds that
$$ Q(V) = \frac{\epsilon_0 A V}{d}$$
so
$$ C \equiv \frac{Q}{V} = \frac{\epsilon_0 A}{d}$$
The capacitance therefore depends on the area of the plates and the distance between them - nothing else.
It's worth noting that one could construct a device which has a more complicated, voltage-dependent capacitance. For example, one could consider a parallel plate capacitor where the plates are held apart by electrically insulated springs. In that case, the distance separating the plates would depend on the electrostatic attraction between the plates, which is determined by the applied voltage. Increasing the voltage would result in a larger charge buildup, which would cause greater attraction between the plates, which would further compress the springs, which would increase the capacitance. Working this out explicitly is an interesting exercise.
But again, for a simple case like the one under consideration in your example, the capacitance is merely a geometrical constant.
Another useful and slightly more intuitive way to think of this is as follows: inserting a slab of dielectric material into the existing gap between two capacitor plates tricks the plates into thinking that they are closer to one another by a factor equal to the relative dielectric constant of the slab. As pointed out above, this increases the capacity of the capacitor to store electric charge.
A good example of this is the electrolytic capacitor, in which the dielectric is an extremely thin layer of aluminum oxide that is formed on the surface of a piece of aluminum foil, with the other "plate" being the chemical paste sitting in contact with the foil. Because the dielectric constant of the aluminum oxide is conveniently large and its thickness exceedingly thin, it is possible to squeeze many microfarads of capacitance into a physically compact package in this way.
Best Answer
By definition, capacitance measures the ability of a system to hold charge. Mathematically, it can be stated as the amount of charge the system can hold per unit potential difference across it.
$$CV = q \tag{1}$$
where $V$ is the potential difference (or potential) of the system, $C$ is the capacitance of the system and $q$ is the charge stored in the system.
An electric field is what causes a change in potential. The relationship between the change in electric potential and the electric field its simplest form can be expressed as follows:
$$V = E.d \tag{2}$$
Consider a parallel plate capacitor. If you keep the amount of charge on the system constant and then reduce the distance between the plates, the potential across the capacitor decreases. As the electric field between the plates depends solely on the surface charge density (assuming that the plates are very large), from equation $(2)$, you can infer that $V$ decreases as $d$ decreases. Therefore, you are holding the same amount of charge for a smaller potential difference. Aha! The capacitor is now able to store more charge per unit potential, therefore its ability to hold charge, that is capacitance, has increased.