First addressing a part of the question: shifting the potential energy does obviously change the potential energy; it just doesn't change the behavior of the system at all. Explanations for the classical and quantum cases follow.
In classical mechanics, the behavior of a system doesn't change when the potential energy is shifted by any constant amount. The simple proof is as follows. The kinematic behavior is determined by forces, and the force is the negative gradient of the potential energy. Therefore, any constant offset term disappears upon taking derivatives:
$$F = -\vec{\nabla} (U(x) + c) = -\vec{\nabla} U(x) -\vec{\nabla} c = -\vec{\nabla} U(x)$$
In quantum mechanics, we have the same situation, but the proof is very different. Consider a Hamiltonian $H$ and add a constant offset, yielding a second Hamiltonian $H' = H + c$. To say that the behavior of the system is the same is to say that all expectation values are the same in the two cases. So consider the following. Suppose $|\psi'(t)\rangle$ satisfies the Schrodinger equation (setting $\hbar = 1$)
$$i\frac{\partial}{\partial t}|\psi'(t)\rangle = (H + c) |\psi'(t)\rangle.$$
Define a transformed state by
$$|\psi(t)\rangle = e^{-ict}|\psi'(t)\rangle.$$
It is straight-forward to show (by using the chain-rule on the left-hand side of the Schrodinger equation), that $|\psi(t)\rangle$ satisfies
$$i\frac{\partial}{\partial t}|\psi(t)\rangle = H |\psi(t)\rangle.$$
Finally, if we take expectation values of an arbitrary $\hat{A}$,
$$\langle\psi'(t)|\hat{A}|\psi'(t)\rangle
= \langle\psi(t)|e^{ict}\hat{A}e^{-ict}|\psi(t)\rangle
= \langle\psi(t)|\hat{A}|\psi(t)\rangle,$$
so that the expectation values of these two states are the same, even though they satisfy slightly different Schrodinger equations. Thus, we get the same behavior, and therefore $H$ and $H+c$ are equivalent Hamiltonians, the second being merely a shift of the first.
