LaTeX doesn't like .gifs: it needs the image in some other form.
Nevertheless, this can be done. But there's a bit of setting up that needs doing.
You need imagemagick available to convert .gif to .png.
You need to set org up so that it will use pdflatex with the --shell-escape enabled. This enables LaTeX to run shell programs while compiling, and is dis-enabled by default for security reasons. (setq org-latex-to-pdf-process "pdflatex --shell-escape --batch %f") Alternatively export to a latex file and run pdflatex --shell-escape [filename].tex at the command line.
You need to tell ox-latex that a .gif file is to be treated as an image file: (setq org-latex-inline-image-rules '(("file" . "\\.\\(pdf\\|jpeg\\|jpg\\|png\\|ps\\|eps\\|tikz\\|pgf\\|svg\\|gif\\)\\'"))) (or customize that variable). Otherwise it will not include your file using as a graphics file but think it is a link, and just export the URL.
You need to add these magical incantations (or some suitable variation) to your latex header -- they depend on the graphicx package, but that is included by default anyway.
#+LATEX_HEADER: \DeclareGraphicsRule{.gif}{png}{.png}{`convert #1 `basename #1 .gif`-gif-converted-to.png}
#+LATEX_HEADER: \DeclareGraphicsExtensions{.gif}
The key one is the first. See https://tex.stackexchange.com/a/4982/5404 for a much fuller explanation. The format I have given is assuming that your .gif files are in the same directory as your .org (or, strictly, as the .tex file it produces). If that isn't the case, you will need to do some more fiddling to make sure TeX can find the files. The answer I linked includes an example.
What this command does is use the --shell-escape to call out to imagemagick, converting foo.gif to foo-gif-converted-to.png i.e. effectively it converts the files on the fly. You end up of course with a load of .png files. Still, it means you can keep your gif for HTML export, so something is achieved I suppose.
