What is the origin of the capacitance formula?
It all comes down to Maxwell's equations. For a parallel plate capacitor we have:
$$\oint \mathbf{E} \cdot d \mathbf{A} = \frac{q}{\varepsilon_0}$$
Where \$\mathbf{A}\$ is the normal surface area vector to the plates, i.e. we construct our area of integration to cover the plates.
For a capacitor it is assumed that the field is uniform i.e. it does not vary on the plates, like this:

The integral becomes simple multiplication:
$$E A = \frac{q}{\varepsilon_0}$$
We can now use the definition for voltage, and substitute the constant electric field:
$$V = - \int \mathbf{E} \cdot d\mathbf{l} = E l$$
Where \$\mathbf{l}\$ is the vector from one plate to the other, following the field lines in the figure above. 

You can substitute to get:
$$V\frac{\varepsilon_0 A}{l} = q$$

We can simply define the constant part as the capacitance: $$C = \frac{\varepsilon_0 A}{l}$$

That is why you get the equation \$Q = CV\$. It is just a constant term that appears in the equations. 

It is important to note that the above line of reasoning is only valid when the assumptions hold. The electric field is not constant in reality. The field lines do something like this:

Also, this analysis is valid only for electrostatics. As soon as you get a magnetic field, it starts influencing the electric field, violating the assumptions. Here is the accuracy of the capacitance for a parallel plate: