It's first important to note that in classical electromagnetism, the $\mathbf{A}$ and $\phi$ fields are not physical in the same way that the $\mathbf{E}$ and $\mathbf{B}$ are. We can't measure them and they aren't uniquely defined.
Gravitational potential energy is a good analogy. Suppose an object is on a table a height $h$ above the ground. We could say that the object has potential energy $U=mgh$, picking the floor to be $U=0$, or that the object has potential energy $U=0$, picking the table to be where $U=0$. In fact, we could choose the gravitational potential energy to be any $U=mgh+C$ for any $C$, as long as we use the same definition of potential energy in the same problem.
Just like we can add any constant to the gravitational potential energy, we can add some additional vector field $\mathbf{V}$ to $\mathbf{A}$. Let's define the new vector potential $\mathbf{A'}=\mathbf{A}+\mathbf{V}$. 499
By the definition of the vector potential, we know $\nabla \times \mathbf{A'} = \mathbf{B}$. Using the properties of the curl, we find $\nabla \times \mathbf{A'} = \nabla \times \mathbf{A} + \nabla \times \mathbf{V} = \mathbf{B}$. However, we know $\mathbf{B}=\nabla \times \mathbf{A}$, so we can write $\mathbf{B}+\nabla \times \mathbf{V} = \mathbf{B}$. Therefore, we see that we can add any $\mathbf{V}$ such that $\nabla \times \mathbf{V}=\mathbf{0}$. Because of an identity in vector calculus, we know that any curl-less vector field can be written as the gradient of a scalar field, say $\psi$.
When we go through the math we find that when we change $\mathbf{A}$ to $\mathbf{A'}=\mathbf{A}+\nabla\psi$ we have to change $\phi$ to $\phi'=\phi-\frac{\partial \psi}{\partial t}$.
So we don't have infinite freedom in gauges. We have the freedom to choose any scalar field $\psi$ and then transform $\mathbf{A}$ and $\phi$ as above. The two most popular gauge choices are the Coulomb and Lorenz, which are detailed in the Wikipedia article you linked to in your question. 418