There are several ways to do this. The basic idea is always the same: You overlay a color and then animate it's hue. To get rid of all other color, you can either convert the footage to black-and-white (which can again be achieved using different techniques) or put the color on an adjustment layer with the blending mode set to color. This is the preferred way to do it, since this way, you can apply the effect to your entire scene at once. Here's a step-by-step guide on how to achieve this effect using the Lumetri Color workspace (which is not available on CS6 and earlier versions).
- Create a new adjustment layer (File → New → Adjustment Layer) and put it over your video clips in the timeline of your sequence.
- Select the adjustment layer in the sequence and change to the Color workspace (Window → Workspaces → Color). The Lumetri Color panel should now be on the right side of the program window.
- In the Lumetri Color panel, under Basic Correction, reduce the Saturation to 0. Your video should now be black-and-white.
- Under Creative, set a color for the Shadow Tint and move the Tint Balance slider all the way to the right (100). Your video should now be monochrome.
- Open the Effect Settings panel (make sure the adjustment layer is still selected) and find the Shadow Tint setting under the Lumetri Color effect (this one is automatically applied once you change a setting in the Lumetri Color panel). Hit the stopwatch icon to activate the animation for that effect property and set the first keyframe (make sure the playhead is positioned at the first frame of the adjustment layer first). Now it's time to get creative, set keyframes at appropriate intervals and change the Shadow Tint to different settings every time. Premiere Pro will interpolate between the values, giving you the color transition effect you wanted.
- Optional: Under Opacity, set the blending mode of the adjustment layer to Color. This way, the original luminosity values are preserved, making the effect more subtle. You can also try Hue for an even more subtle effect or change the opacity of the adjustment layer. This will reduce the color overlay effect, allowing some of the original clip colors to come through.
Workaround for CS6
Since the Lumetri Color panel doesn't exist in CS6, you will need to use another color correction effect instead. The basic idea will stay the same though. You can for example use the Tint effect in the same way as described above (you will have to set keyframes for both Map Black To and Map White To, since there is no balance slider in this effect). With the introduction of the Lumetri Color panel, a lot of the old CS6 color correction effects got deprecated in the new CC version. If you are still on CS6, you could for example also use the Three-Way- or Fast Color Corrector to get similar results.
Or just do it in After Effects using Layer Styles → Color overlay, set the Blend Mode of the effect to Color and animate the Color.