Photons do not move at all. Light propagates at c in a vacuum. A photon describes the interaction of the propagated light with another phenomenon(such as a detector).

...in a vacuum

Technically, photons always travel at c. Slow moving light is caused by the medium continually absorbing, delaying, then re-emitting the photon, or by other stuff which I won't pretend to understand [1]. Either way, rest assured that electromagnetic propagation always travels at c WRT any inertial frame.

[1] http://en.wikipedia.org/wiki/Slow_light

Still, I don't see how the photons would be travelling at different velocities in the same medium.

They are all moving at the same speed, yes. They are moving in different directions, meaning they have different velocities, but the components of that vector will add up to c.