Why gauge transformations does not/cannot change a quantum state?
This is perhaps easier to see in ordinary quantum mechanics.
Consider a particle in an electromagnetic field, whose Schrodinger equation is given by
$$i\hbar \frac{\partial \psi}{\partial t} = \frac{1}{2m}(-i\hbar \nabla -q \mathbf{A})^2\psi+q\phi\psi$$
Under a $U(1)$ gauge transformation, the scalar and vector potentials transform as $$\phi \to \phi- \frac{\partial \alpha}{\partial t}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\mathbf A \to \mathbf A + \nabla \alpha$$
where $\alpha = \alpha(t, \mathbf x)$ is a generic function. One can check that the Schrodinger equation remains invariant only if the wavefunction too transforms under the gauge transformation, $$\psi \to e^{iq \alpha/\hbar} \psi$$
We see that the gauge transformation only changes the phase of the wavefunction. As we know, in quantum mechanics states are defined only up to a phase. Therefore at the level of rays in the Hilbert space a gauge transformation sends a ray to the same ray, i.e. it is the identity transformation on states.
If instead of having a time and/or position dependent $\alpha$ we take $\alpha$ constant, then this is also a $U(1)$ phase transformation. It acts only on the wavefunction, and it is again the identity transformation on states.
However, there are also different types of global $U(1)$ transformations which do not lead to identity transformations on states. For example, consider the harmonic oscillator Hamiltonian $$H = a^\dagger a$$ This is invariant under the transformation $$a \to e^{-i\theta} a\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, a^\dagger \to e^{i\theta} a^\dagger$$ which is a global $U(1)$ phase transformation. This transformation is given by a unitary operator $G$ in such a way that $$a \to G a G^\dagger = e^{-i\theta} a\\ a^\dagger \to G a^\dagger G^\dagger = e^{i\theta} a^\dagger$$ One can check that a suitable operator is given by $$G = \exp{(i \theta a^\dagger a)}$$ However $G$ is not the identity transformation on states, as its action on a generic wavefunction $\psi$ is not given by "multiplication by a phase".
In other words, a gauge transformation is a "do-nothing" transformation on states, or equivalently a phase transformation on vectors. However, a $U(1)$ phase transformation on operators is not necessarily a phase transformation on states.
TL:DR:
You add extra terms in the Lagrangian at the classical level, which fix the gauge classically. As operator equations on the quantum level, they weed out states that were nonphysical and arose because you used terms in the Lagrangian that were nonphysical but kept manifest Lorentz invariance. In effect, your new Hilbert space is SMALLER than the Hilbert space of the gauge invariant lagrangian and contains only the useful physical states. The redundancy has been removed via a constraint equation. The gauge redundancy in your Lagrangian, has now been removed from the states in Hilbert space, by construction.
In quantum mechanics, the physical states are not the vectors $|\psi\rangle$, but the RAYS, that are defined by the equivalence class of all $$\{\Psi_i\} \hspace{7mm} \Psi _i=c|\psi\rangle \forall c\in C$$ i.e. all multiples of the state vector, $c=|c|e^{i\phi}$ ofcourse. This is because only the amplitude $|\psi|^2=\langle\psi|\psi\rangle$ and expectation values $\langle A\rangle=\langle\psi|A|\psi\rangle/|\psi^2|$ is a measurable quantity, not the state itself.
If the states are normalised to 1, then $|c|=1$ too, and thus $$c=e^{i\phi}\in U(1)$$
Thus, the elements of the Hilbert space that are related by $U(1)$ transformations are equivalent(they lie on the same ray, and are thus the same physical state.) Conversely, the transformation $$\psi\to \psi'=e^{i\phi}\psi$$ is a gauge transformation since $\psi$ and $\psi'$ lie on the same ray. Colloquially, “states are uniquely defined only up to a phase”. You will see statements like 'fixing the arbitrary phase to unity'- that is essentially fixing the gauge.
Interesting comments can be made about the nature of the phase $\phi$(is it global, what about other unitary transformations, superselection rules, etc). I recommend Weinberg Vol 1, Ch-2 for details.
As an interesting aside, you can read about cocycles (there is an article by Jackiw, I will try to find it). Projective representations (the ones we see in QM) are essentially implemented by $2$-cocycles, would be the equivalent statement to all of the above in that context. Roughly, it means the group composition law is relaxed to allow arbitrary phases in the representation. Weinberg uses the same principles.
EDIT:
The quantum states are defined to be the vector space over which the representations of the Poincare groups act, the operators being the fields.
Because we insist on manifest Lorentz invariance, we often have to include extra terms in our Lagrangian that are redundant. For example the 4 vector $A_\mu$ is used to keep manifest Lorentz invariance, while the photon has only 2 degrees of freedom.
In principle, one can for example use only $E,B$ instead of $A_\mu$ and never see these 2 extra redundancies. But one then loses MANIFEST(and not genuine) invariance. So, it's a choice between what you want-manifest Lorentz invariance, or only writing down the physical degrees of freedom.
In practice, the former is more useful and is preferred. The latter causes problems-if you have nonphysical degrees of freedom, you WILL have nonphysical quantum states and you cannot help that(for example, negative norm states or 'ghosts') yet. You clearly have two issues-(a)your Hilbert space has meaningless states; (b) your fields carry redundant information, even at the classical level.
So, you fix this by being careful how you quantize the field and defining the Hilbert space on which they act. You usually add another spurious term to the Lagrangian to 'fix the gauge' at the CLASSICAL level(the E.O.M for this spurious fields are the gauge fixing equations), and then, you use the equations as an operator equation on your Hilbert space to remove the spurious states of $A_\mu$ that crept in.
In essence, this is analogous to doing something like selection rules-a very crude(and mostly incorrect, but instructive) example would be constructing simultaneous eigenkets of, say, the Hamiltonian and Parity. Suppose there were an eigenstate of $H$ that wasn't a parity eigenstate — you wouldn't include it in your Hilbert space. Ofcourse, this situation never happens with parity because it's a true genuine symmetry; but supposing it wasn't — supposing the Hamiltonian didn't distinguish between states of opposite parity but the physical system did; you would continue to work with $H$ eigenkets, but restricting to those which are also parity kets. You use parity as a CONSTRAINT equation and stick to H eigenkets, much like you use $\langle \partial A\rangle=0$ as constraint equation and use $A_\mu$ eigenkets. This is Gupta Bleur Quantization.