I just went through this.  Try this.
Step 1 - Set your email to HTML
To do this, click on TOOLS, OPTIONS, MAIL FORMAT

Step 2:
Select HTML.  Next make sure you deselect the “use MSOffice word 2003 to
edit e-mail messages” and the one below it.  That will ensure that your
messages are sent in HTML only.

Step 3:

Now at the bottom of that same Mail Format window you will see your
signature area.  Click on the ‘signatures’ button.



Step 4:

Click on the ‘new’ button.



Step 5:

Enter a name for your Signature and make sure you have the ‘start with blank
signature’ with a bullet in it.  Then click the next button.



Step 6:

At this stage you can enter any text you would like as a permanent part of
the signature.Then click on the ‘ADVANCED EDIT’ button.

Step 7:

A popup window will ask for you next move.  Click the yes button.  At this
point, Microsoft Word should open.  



Step 8:

Now you can click on INSERT, PICTURE, FROM FILE. Go to your Desktop to
locate the GIF file or link and double-click the file. ***Please note:  It
will now appear on your page - not be animated.


Step 9:

Go to FILE and SAVE AS (The file will probably save in what is called a
"Signature" folder.)



Step 10:

In your toolbar along the bottom of your computer screen, click on
"OUTLOOK".  The dialog box for Signatures should re-appear and you should see
the animated graphic in the preview box.

Step 11:

Click OK



Step 12:

In the "Signature for New Messages" box, click the drop down menu and select
your signature (or whatever the name of the file you designated).



Step 13:

Click APPLY and OK



Step 14:

Open up a new email message and, at this point, the animated graphic will
appear!  You may need to click on it (only once to highlight it)