The important point of any "gauge symmetry" is that it describes a situation, where the equations of motion do not completely determine the quantities to be calculated, but this "incompleteness" has no consequences for the physics described.
In the case of classical electromagnetism, what uniquely describes the physical situation is the solution of Maxwell's equations together with the equations of motion for the charged matter, and this set of equations has unique solutions.
Of course, usually you consider a somewhat simpler situation, and we'll stick to that to begin with, that you want to find the electromagnetic field ##(\vec{E},\vec{B})## for a given distribution of charges and current densities, ##(\rho,\vec{j})##.
Now to find such solutions one introduces the electromagnetic potentials ##(\Phi,\vec{A})##. The reason is to simplify the math. The idea is that mathematically the two homogeneous Maxwell equations are constraint equations for the electromagnetic field (in SI units):
$$\vec{\nabla} \times \vec{E}+\partial_t \vec{B}=0, \quad \vec{\nabla} \cdot \vec{B}=0,$$
i.e., these equations have nothing to do with the charge-current distribution but relate the fields to each other. So the idea is to exploit these constraints to introduce the potentials. Starting with the 2nd equation (Gauss's Law for the magnetic field), we see that there's a vector potential, ##\vec{A}## such that
$$\vec{B}=\vec{\nabla} \times \vec{A}.$$
Already at this very first step, it's clear that ##\vec{A}## is not unique, i.e., if you consider ##\vec{B}## known for a moment it's clear that any other vector potential
$$\vec{A}'=\vec{A}-\vec{\nabla} \chi,$$
where ##\chi## is an arbitrary (!) scalar field, leads to the same ##\vec{B}##, because ##\vec{\nabla} \times \vec{\nabla} \chi=0## for any field ##\chi##.
But just let's go on. Pluggin this to the first homogeneous Maxwell equation (Faraday's law) leads to
$$\vec{\nabla} \times (\vec{E}+\partial_t \vec{A})=0.$$
Now if the curl of vector field vanishes, it's clear that you can find a scalar potential for this field:
$$\vec{E}+\partial_t \vec{A}=-\vec{\nabla} \Phi \; \Rightarrow \; \vec{E}=-\vec{\nabla} \Phi-\partial_t \vec{A}.$$
The same calculation we can do with ##\vec{A}'##, but since ##\Phi## depends on ##\vec{A}## there must also be a different ##\Phi'##:
$$\vec{E}=-\vec{\nabla} \Phi' -\partial_t \vec{A}'=-\vec{\nabla} \Phi' - \partial_t (\vec{A}-\vec{\nabla} \chi) = -\vec{\nabla} \Phi-\partial_t \vec{A}$$
From this you get
$$\Phi'=\Phi+\partial_t \chi.$$
This implies that the potentials are only determined up to a gauge transformation,
$$\vec{A}'=\vec{A}-\vec{\nabla} \chi, \quad \Phi'=\Phi+\partial_t \chi,$$
i.e., in introducing the potentials the Maxwell equations can determine them up to an arbitrary choice of a scalar field ##\chi##.
Since any ##\chi## will do, you can impose an arbitrary additional equation constraining the potentials. This can be used to simplify the task of solving also for the inhomogeneous Maxwell equations, which are the equations that relate the em. field to the sources, ##\rho## and ##\vec{j}##:
$$\vec{\nabla} \times \vec{B}-\epsilon_0 \mu_0 \partial_t \vec{E}=\mu_0 \vec{j}, \quad \epsilon_0 \vec{\nabla} \cdot \vec{E}=\rho.$$
Expressing ##\vec{E}## and ##\vec{B}## in terms of the potentials, leads to
$$\vec{\nabla} \times (\vec{\nabla} \times \vec{A}) - \epsilon_0 \mu_0 (-\partial_t^2 \vec{A} -\partial_t \vec{\nabla} \Phi)=\mu_0 \vec{j}$$
and
$$-\vec{\nabla} \cdot (\partial_t \vec{A} + \vec{\nabla} \Phi)=\rho/\epsilon_0.$$
The first equation can be rewritten as
$$(\epsilon_0 \mu_0 \partial_t^2-\Delta) \vec{A} + \vec{\nabla} \cdot (\vec{\nabla} \cdot \vec{A} + \epsilon_0 \mu_0 \partial_t \Phi)=\mu_0 \vec{j}.$$
Now we remember that we can impose one arbitrary condition on the potentials. It's obvious that we get the most simple equations for ##\vec{A}## by demanding
$$\vec{\nabla} \cdot \vec{A}+\epsilon_0 \mu_0 \partial_t \Phi=0,$$
which is known as the "Lorenz-gauge condition". In general one calls it a "gauge fixing" when imposing an arbitrary constraint on the potentials. The physics won't change although of course the potentials depen choosing the gauge-fixing condition, because the observable fields, ##\vec{E}## and ##\vec{B}## don't depend on this "choice of gauge".
The equation for ##\Phi## also simplifies in choosing the Lorenz-gauge condition by substituting ##\vec{\nabla} \cdot \vec{A}=-\epsilon_0 \mu_0 \partial_t \Phi## into that equation:
$$(\epsilon_0 \mu_0 \partial_t^2-\Delta) \Phi=\frac{1}{\epsilon_0} \rho.$$
It's clear that ##\epsilon_0 \mu_0=1/c^2## has the dimension of ##1/\text{velocity}^2##, and the values of ##\epsilon_0## and ##\mu_0## show that ##c## is the speed of light, which lead Maxwell to the conclusion that light is an electromagnetic wave since what we derived, choosing the Lorenz-gauge fixing, are wave equations for ##\vec{A}## and ##\Phi##.
There are also other popular gauge conditions. One also commonly used is the Coulomb-gauge condition,
$$\vec{\nabla} \cdot \vec{A}=0.$$
Then the equation for ##\Phi## simply looks as in electrostatics,
$$\Delta \Phi=-\frac{1}{\epsilon_0} \rho,$$
and you get another somewhat more complicated equation for ##\vec{A}##. At the end you get again the same solution for the electromagnetic field, because one can explicitly show, that there's a gauge field ##\chi## such that the potentials from the Lorenz-gauge and from the Coulomb-gauge fixing are gauge transformations of each other. For details, see
https://arxiv.org/abs/2006.11598
https://doi.org/10.1088/1361-6404/abc137
