I am not sure if I've done it right. I copied qgif4.dll into plugins\imageformats subfolder of where my exe is deployed.
It still does not work with gif.
I am using prebuilt Qt binaries that came with 2009.03.