How do I get particles to change color over time?
Two Techniques to Have Particles Change Color Over Time

I discovered two ways to have particles change color over time, but they both start the same way:  


First, create an object to be the particles for the particle system. I used a sphere in the videos below.  
Create an object (I used a plane) and add a particle system to it with these settings:  


In the Emission section for the videos below, I have:
Number = 1000
Start = 1
End = 200
Lifetime = 200
In the Velocity section, set Normal to a desired value. I used 7.0 in the videos below.  
In the Render section, select Object and then for Dupli Object select the object you made for the particles in step 1.  

Now add a material to the particle object. Here is where I discovered two different node tree configurations to create two different effects: 


Effect #1: Each particle is a different color &amp; stays that color over it's entire lifetime



For this technique the node tree for the particle object's material is made like this:  

 

NOTE: For this effects, the Divide node's Value must be set to the number of particles in the particle system (here, it's 1000)

This technique was developed by kubo on BlenderArtists.org.

Effect #2: All particles change color over the course of their lifetime



This is the node tree for this technique:  

  

NOTE: For this effects, the Divide node's Value is set to a low number (here, it's 50), not to the number of particles  

This technique was developed by Vader and Greg Zaal here on StackExchange.

Previewing the Effect

If you want to see the colors changing in the 3D Viewport, the display mode must be set to Rendered