I use The GIMP. It's an open-source program a lot like PhotoShop. It opens the animation into frame layers. I just scaled the whole image to 100x100 and then started taking out frames and increasing the delay between to bring the KB-size down. Usually every-other one worked, but the human female's mashed-potato was just over the 40K limit, so I only had to take out I think 4 frames total and at the far right and left, there wasn't a lot of differences frame-to-frame. Oh, I just /babbled. /lol o^-^o

Starting with the background, each layer is a frame. By default it uses combine and 100ms. To change the delay between frames, put (Xms) in the frame name, where X is a number of milliseconds divisible by 10. You can always check how the animation looks by going to Filters->Animation->Playback... To change whether it replaces all the previous frames with the new frame or combines it (like by overlaying a transparent layer), put either (combine) or (replace) at the end.
You can Filters->Animation->Optimize (for GIF) it, which makes it figure out which pixels don't change from one frame to the next and make them transparent, cutting down the end file size. This opens the optimized version in a new window, leaving the unoptimized version alone.
When you save, put the filename in with a .gif extension and then in the dialog boxes, tell it to "Save as Animation". On the next dialog box, you can tell it what the "_Delay between frames where unspecified" is, and if you want it to "Loop forever" or run just once.
Try opening the icon I've used on this post of the elf dancing. It has to use the (replace) tag on each frame because it has a transparent background.
On this one, The background is solid, so I used combine to add the letters which are on a transparent background.
Play around with it, find some animated gifs, open then up, and see what techniques were used. That's mostly how I figured it out.