There is a chain of dependencies that you need to check. It starts with libgd, then the GD module, then GD::Graph.

So you may need to recompile libgd ( with the latest version), then rebuild GD, then rebuild GD::Graph to get gif support. From the GD readme:

 libgd can now be built with support for one or more of the PNG, GIF, 
+XPM or  JPEG formats. If one or more of these formats are not support
+ed by libgd, then the corresponding GD::Image methods will be unavail
+able.                               
.......                                                               
+    
   As of libgd 2.0.33, GIF support is always compiled in, so (for the 
+time being!)   this is a safe fallback.
[download]