First, it has to be an animated .gif, like everybody's stated. Generally, .gifs are never under 75x75 dimensions, though, so here's a quick guide to fixing that.
1. Open your .gif in a program that supports multiple layer .gifs (I use GIMP, a free image editing software).
2. Go to the "Image" tab on the toolbar and select "Scale Image"

3. If the image is taller than it is wide, enter 75 for the bottom value. If it's wider than it is tall, enter 75 for the top value. If it's square, don't worry about it and enter 75 for whichever you want.

4. Save as a new .gif, using the following settings:


5. Upload it as your avatar.
Huzzah! Animated avatar.
