Why does gauge invariance in electrodynamics mean that there are redundant degrees of freedom? It is possible to choose different gauges in electrodynamics. I am familiar with two of them: Coulomb gauge and Lorenz gauge. Let us stick to the Coulomb gauge. It sets $$\nabla\cdot\vec{A}=0.$$ The wisdom is that with this choice the physical electric and magnetic fields $\vec{E},\vec{B}$ do not change. But there is more to it. It is also important for me to understand why this gauge condition implies that there are superfluous degrees of freedom. 
What are these superfluous and non-superfluous degrees of freedom? With which mathematical quantities should we identify them? 
First of all, at each spacetime point, we have four numbers $$\phi(\vec{x},t),A_1(\vec{x},t),A_2(\vec{x},t),A_3(\vec{x},t).$$ I understand these four numbers as the four degrees of freedom. Now, Coulomb gauge means that the latter three can be related, without any loss of generality, through the differential equation $$\partial_1A_1+\partial_1A_2+\partial_3A_3=0.$$ Given this, how to understand the rest?
 A: Gauge invariance just happens to be the technical term people chose to indicate that redundant electromagnetic degrees if freedom. I guess that answers the question in the title.
In your example you as they say fixed the gauge by choosing $\vec \nabla \times \vec A=0$. That is all there is to it. 
A: The existence of "superfluous" degrees of freedom is implies not so much by the gauge condition, but by the gauge transformations itself. 
The point is that you four "numbers", i.e. functions, $\phi$ and $A_i$ are equivalent to four other functions, $\phi + \dot\alpha$ and $\vec A+\text{grad}\, \alpha$ for any function $\alpha(t,x)$. (I might have mixed up a sign somehwere, but that doesn't matter here.) So, for example, the values of the potentials at any given point in spacetime can be changed to any other value, and physically measurable quantities have to be gauge invariant -- such as the $\vec E$ and $\vec B$ fields and certain contour integrals (cf. Aharonov-Bohm effect). 
The gauge conditions you impose serve to fix the gauge transformations. Thus, they 


*

*need to be attainable by a gauge transformation (i.e., you should be able to find an $\alpha$ such that the gaueg transformed potentials satisfy the condition), and

*preclude further gauge transformations (i.e., there should be no other such $\alpha$).

A: The scalar and vector potentials are gauge covariant which is to say $\Phi' \ne \Phi,\,\mathbf{A}' \ne \mathbf{A}$ where
$$\Phi'(\mathbf{x},t) = \Phi(\mathbf{x},t) - \frac{\partial}{\partial t}\chi(\mathbf{x},t)$$
$$\mathbf{A}'(\mathbf{x},t) = \mathbf{A}(\mathbf{x},t) + \nabla\chi(\mathbf{x},t)$$
The electric and magnetic fields, on the other hand, are gauge invariant since the gauge transformation above leaves the fields unchanged
$$\mathbf{E}' = -\nabla\Phi' - \frac{\partial}{\partial t}\mathbf{A}' = -\nabla\Phi + \frac{\partial}{\partial t}\nabla\chi - \frac{\partial}{\partial t}\mathbf{A} - \frac{\partial}{\partial t}\nabla\chi = -\nabla\Phi - \frac{\partial}{\partial t}\mathbf{A} = \mathbf{E}$$
$$\mathbf{B}' = \nabla\times\mathbf{A}' = \nabla\times\mathbf{A} +\nabla\times\nabla\chi = \nabla\times\mathbf{A} = \mathbf{B}$$
Thus, it must be that $\Phi$ and $\mathbf{A}$ have a non-physical degree of freedom which is essentially the freedom to choose the gauge function $\chi(\mathbf{x},t)$.
Choosing a gauge amounts to specifying (in full or in part) the gauge function $\chi$.  For example, an arbitrary vector potential $\mathbf{A}$ can be made to satisfy the Coulomb gauge with a gauge function $\chi$ that satisfies
$$\nabla\cdot\nabla\chi = -\nabla\cdot\mathbf{A}$$
such that
$$\nabla\cdot\mathbf{A}' = \nabla\cdot(\mathbf{A} + \nabla\chi) = 0$$
