こんにちは

●ffmpegの導入について
Linuxサーバ等はffmpeg自体のコンパイルを行う必要があります。
一般的な共有レンタルサーバでは導入は難しいかもしれません。
またコンパイル時のオプション設定により、扱える動画形式等も変わるので多少の知識が必要となります。
サーバ管理者と交渉してみて下さい(´ー｀

●難易度
ffmpegの適切な導入が一番の難関になるかと思います。
導入さえ済めば変換自体はさほど難しくありません。

幅広い携帯動画に対応させたい場合は、
特に適切にオプション設定を弄る必要があります。

●実際の変換処理
1.元になる動画をサーバに保存する
　例)WEBフォームからの送信、メールからの送信等で

2.保存された動画を引数にしてffmpegを呼び出す。
　例)Perlで書いた場合
　　$command = "/usr/local/bin/ffmpeg -y -i INPUT.3gp -vcodec flv OUTPUT.flv";
　　$output = `$command`;

の2工程でflvが生成出来ます。
(変換中の待機処理等、細かい処理を除く)

●参考
windows版のffmpegでしたら『携帯動画変換君』等にコンパイル済のモノが添付されていますので、
ローカル環境でのテスト開発等に利用できます。