Why does red light travel faster than blue light? I know that light of all frequencies travel at the same speed in vacuum.
But I wonder why their speed differ in any other medium, why does red light travel faster if it has less energy than blue light?
 A: Jon Custer hinted at something, which I think is best explained via an analogy.
Imagine you can walk along a pavement at 4mph. When the pavement is empty, it takes you an hour to travel four miles. But when the pavement is crowded, you're dodging around people and bumping into them. You're still walking at 4mph, but it takes you an hour and a half to travel the four miles. And if you're a little old lady with short little steps walking at 4mph, you're held up more than if you're a big guy with long strides walking at 4mph. Now let's look at your questions again:
But I wonder why their speeds differ in any other medium? 
Because the light interacts with the material, and those interactions are wavelength dependent.
And why Red light travels faster while it has less energy than blue light?
Because the light interacts with the material, and those interactions are wavelength dependent!

A: Feynman:
The correct picture of an atom, which is given by the theory of wave mechanics, says that,so far as problems involving light are concerned, the electrons behave as though they were held by springs. So we shall suppose that the electrons have a linear restoring force which, together with their mass $m$, makes them behave like little oscillators, with a resonant frequency $\omega_0$.
...........The electric field of the light wave polarizes the molecules of the gas,producing oscillating dipole moments.The acceleration of the oscillating charges radiates new waves of the field.The new field,interfering with the old field,produces a changed field which is equivalent to a phase shift of the original wave.Because this phase shift is proportional to the thinkness of the material ,the effect is equivalent to having a different phase velocity in the material''.
Considering the above model the expression for refractive index can be derived which shows the refractive index depends on the frequency of the light and since speed of the wave through the meterial depends on the refractive index so different frequency waves move with different velocities.
Here is the Feynman's derivation 
http://www.feynmanlectures.caltech.edu/I_31.html
A: Most of the answers were helpful indeed but I thought it in a different way to say that Red light travels faster compared to blue light.
Think it as the example of a prism.

We can see that the red light is scattered the least while the violet is scattered the most.
Now ask yourselves, How is deflection related to speed of an object? It's an inversely proportional relationship. From the prism, we can conclude that the red light must be traveling through a greater speed compared to blue light as it is deflected the least.
A: $c_0^2 = \frac{1}{ε_0μ_0}$ in vacuum. Permitivity and permeability (in materials) depend on frequency, in general.
+
In material you have $\epsilon=\epsilon_r \epsilon_0$, $v^2 = \frac{1}{εμ}$, where $v$ is a phase velocity of the light. - see http://en.wikipedia.org/wiki/Permittivity, where is a also a picture of frequency dependence of $\epsilon$.
