Philippe Roubal has been experimenting with ways to animate footprints in the sand. He published the results of his work in a new tutorial.
Philippe's method works by applying a displacement texture on a finely subdivided mesh. Next, the texture is masked by a gradient layer that is animated to reveal the footsteps one by one. The result is quite convincing - you will find a sample animation at the bottom of the page.
The result looks quite convincing although I wonder if you really need displacement - would a simple bump map achieve the same effect?