ImageMagickにあるconvertコマンドを利用することで画像の形式を変換することが出来ます。
Debian系のOSなら
sudo apt-get install imagemagick
でインストールできます。
Windowsはここから
http://www.imagemagick.org/script/download.php#windows
実際の形式変換は
convert before_image.gif after_image.png
で実行できます。
jpegへ変換する際は
convert before_image.png -quality 100 after_image.jpeg
と圧縮率を指定して実行します。
-quality 100は圧縮率100のことだそうです。（詳しいことは分からない...）
ImageMagickがサポートしているフォーマットはidentify -list formatで確認することが出来ます。