Gauge invariance is simply a redundancy in the description of a physical system. I.e. we can choose from an infinite number of vector potentials in E&M.
For example, an infinite number of vector potentials can describe electromagnetism by the transformation below
$$A(x) \to A_\mu(x) + \partial_\mu \alpha(x)$$
Choosing a specific gauge (gauge fixing) can make solving a physical problem much easier than it would be if you did not fix a gauge.
Normally one chooses the Coulomb gauge: $\nabla \cdot A = 0$.
It should be stressed that gauge invariance is NOT a symmetry of nature and you cannot measure anything associated with it.
Gauge invariance is most useful in quantum field theory and is crucial in proving renormalizability. Additionally S-matrix elements in QFT require a local Lagrangian and hence gauge invariance.
As an example of why we would introduce the vector potetial $A^\mu$ consider the Aharonov-Bohm effect which arises due to global topological properties of the vector potential. There are still other reason gauge invariance makes life easy, reducing degrees of freedom of the photon in the so-called covariant or $R_\xi$ gauge, causality, etc. Essentially the utility of gauge invariance doesnt become entirely evident until one starts trying to work through quantum field theory. Now it is an utterly crucial property of modern physics and we may very well be lost without it! :D
