Creating the Graphic.
First thing you will have to do is create Several Effects
Using one basic graphic( 16x16 will do fine )
Create one effect for each of the terrain types you wish footprints to appear in.
For the purpose of this tutorial I have created one Mud print type graphic
Start with a basic Graphic like this

When placed into the effects change its color.

once that is done add another frame and in the second frame scale it down.
This will cause the footprint to shrink and fade away.