You'll need an image editing program, like Photoshop, or the GIMP. You'll also need VTFEdit.
For every frame of your spray, you will need a separate tga file. I'm not going to go into detail about editing your gif into seperate frames, that one is on you. At 128x128, you can have up to seven frames. Name your spray images something like:
spray001.tga spray002.tga ... spray007.tga
Open up VTFEdit. Go to File > Import. Ctrl+click each .tga file, and import the whole bunch. In the dialog that pops up, deselect 'Generate MipMaps' but leave all else at the defaults. You should now see your spray off to the side. Go to File > Save, and save yourspray.vtf into:
...\Team Fortress 2\tf\materials\vgui\logos
Start up TF2 and import yourspray.vtf via the in-game spray importer.
--- You don't have to be Awesome to have Common Sense and Foresight Rule #59: I will never build a sentient computer smarter than I am