Convert Gif to PDF

I've done something similar, using a combination of Graphic Converter and Automator.

Automator has a "Combine PDF Pages" action that works nicely, but first you have to get your images into PDF format. For some reason Automator's "Change Type of Images" action doesn't allow you to select PDF as its output file type, so unfortunately I don't think you can do it in one handy Automator workflow. But since you can do that initial conversion with Graphic Converter, it's just an additional step.

GC has a "Convert and Modify" screen that will allow you to select all your GIFS and convert them to individual PDFs in one big step. Then you can use Automator's "Combine PDF Pages" action to merge these PDF files together.

The full Automator workflow I use (as a Finder plugin) is this:

Get Specified Finder Items
Sort Finder Items (by name in ascending order)
Combine PDF Pages (by Appending pages)
Move Finder Items (to Desktop)
Rename Finder Items (Add text: "Combined PDF" before name)

It's worked for me, so I hope that helps!

Pres

Preston's suggestion sounds like a solid one. If you don't have Graphic Converter though, you could (in theory, I haven't tried it) use Preview's Print Images or Finder's Print Finder Items action to print to a CUPS-PDF printer, and then stitch up the results of that.