Why does wavelength change as light enters a different medium? When light waves enter a medium of higher refractive index than the previous, why is it that:
Its wavelength decreases?
The frequency of it has to stay the same?
 A: (This is an intuitive explanation on my part, it may or may not be correct)
Symbols used: $\lambda$ is wavelength, $\nu$ is frequency, $c,v$ are speeds of light in vacuum and in the medium.
Alright. First, we can look at just frequency and determine if frequency should change on passing through a medium.
Frequency can't change
Now, let's take a glass-air interface and pass light through it. (In SI units) In one second, $\nu$ "crest"s will pass through the interface. Now, a crest cannot be distroyed except via interference, so that many crests must exit. Remember, a crest is a zone of maximum amplitude. Since amplitude is related to energy, when there is max amplitude going in, there is max amplitude going out, though the two maxima need not have the same value.
Also, we can directly say that, to conserve energy (which is dependent solely on frequency), the frequency must remain constant.
Speed can change
There doesn't seem to be any reason for the speed to change, as long as the energy associated with unit length of the wave decreases. It's like having a wide pipe with water flowing through it. The speed is slow, but there is a lot of mass being carried through the pipe. If we constrict the pipe, we get a jet of fast water. Here, there is less mass per unit length, but the speed is higher, so the net rate of transfer of mass is the same.
In this case, since $\lambda\nu=v$, and $\nu$ is constant, change of speed requires change of wavelength. This is analogous to the pipe, where increase of speed required decrease of cross-section (alternatively mass per unit length)
Why does it have to change?
Alright. Now we have established that speed can change, lets look at why. Now, an EM wave(like light), carries alternating electric and magnetic fields with it.  Here's an animation. Now, in any medium, the electric and magnetic fields are altered due to interaction with the medium. Basically, the permittivities/permeabilities change. This means that the light wave is altered in some manner. Since we can't alter frequency, the only thing left is speed/wavelength (and amplitude, but that's not it as we shall see)
Using the relation between light and permittivity/permeability ($\mu_0\varepsilon_0=1/c^2$ and $\mu\varepsilon=1/v^2$), and $\mu=\mu_r\mu_0,\varepsilon=\varepsilon_r\varepsilon_0, n=c/v$ (n is refractive index), we get $n=\sqrt{\mu_r\epsilon_r}$, which explicitly states the relationship between electromagnetic properties of a material and its RI.
Basically, the relation $\mu\varepsilon=1/v^2$ guarantees that the speed of light must change as it passes through a medium, and we get the change in wavelength as a consequence of this.
A: The energy of the light is related to the frequency; when the light enters the medium there are interference patterns that cause the apperent speed of light to change; if the frequency changed, the energy would not be conserved. The wavelength changes to balance the change in speed.
A: Here is a slightly different take on this using the boundary conditions for electromagnetic fields at an interface.
A key boundary condition, that is derived from Faraday's law, is that the component of the E-field tangential to the boundary must be continuous.
So take an EM wave travelling at normal incidence with the electric field solely in a direction tangential to the boundary. Let's represent it as ${\bf E} = E_I \sin (\omega t - kx) \hat{j}$, where I have chosen that the wave travels towards positive $x$ and is polarised in the $y$ direction.
Let the interface be the plane at $x=0$.
The continuity condition then demands that the E-field of the incident wave plus the E-field of the reflected wave must equal the E-field of the transmitted wave, all at $x=0$. This is a condition that must be satisfied for all value of $t$.
Hence
$$ E_I \sin (\omega_I t) + E_{R} \sin (\omega_R t) = E_T \sin (\omega_T t)$$
For time-invariant E-field amplitudes, the only way this can be true for all $t$ is if $\omega_I = \omega_R = \omega_T$. i.e. the frequency of the transmitted wave is the same as that of the incident wave. Given that the speed of light in a medium is changed (for reasons explained in Manishearth's answer), then the wavelength of light in the medium must also change.
A: It's because $v=c/n \equiv \lambda~\nu$, so either $\lambda$ or $\nu$ must change for adapting to new wave momentum as it enters other medium and propagation speed drops. Energy conservation law filters-out change of $\nu$ possibility, because $E=h \nu = \text{const}$ for a photon. So what we left with is $\lambda$.
