How to make / generate the trailing effect? If an object is moved from Point A to Point B using the Follow Path constraint, I want it to leave behind a trail of color behind it. 

Note : I have enabled Freestyle under which i have unchecked Use Surfaces / Solid in the Layers Tab -- NO TEXTURES are a set to the object.

This is what the render output looks like:



UPDATE : Since, freestyle has it's limitations, I was thinking of parenting a ribbon at the bird's tail, that would give a similar trailing effect, however, I want the ribbon's Freestyle Strokes to fade away long it's length. Also, what is the most suitable cloth modifier preset to simulate a ribbon?
I can't fully get you reference to your freestyle setup, but a simple way could be using a mesh deformed by and also following the curve, using a blend texture influencing the mesh alpha.
This is a single color example, but it should be possible use a rainbow style texture...

you could combine such a trail with the freestyle based animation, perhaps... maybe using different render layers.
edit: since you asked here is a possible similar setup with cycles (renders a bit slower)

edit: since you asked, here is the .blend related to the last example (cycles)

Note: the animation is not done with follow path here, but animating the Y location after setting a curve deform modifier... the effect is similar, though.