Depends a lot on what you're using.
On photoshop this is relatively easy to achieve using tweening and opacity.
Basically you'll have two layers, one with the original color, and one with the new. On frame 1 you want to set the opacity of the new color layer to 0%. On frame 2 you'll want to set the opacity of the new color to 100%. Then hit the tween button and it will fade the colors together for you:
Apologies for the crappy tutorial quality.