On a Linux server you can do this with mencoder + flvtool2 (both are free).

It works for most video formats such as mpg, avi, wmv, rm, 3gp, mp4, asf, mpeg, mov, etc.

Php examples:

Step 1.
in this example someone has uploaded a file called uploadedfile.wmv. Mencoder creates an flv file called uploadedfile_temp.flv

exec("/usr/local/bin/mencoder /your/dir/uploadedfile.wmv -o /your/dir/output/uploadedfile_temp.flv -of lavf -oac mp3lame -lameopts abr:br=56 -ovc lavc -lavcopts vcodec=flv:vbitrate=400:mbd=2:mv0:trell:v4mv:cbp:last_pred=3 -lavfopts i_certify_that_my_video_stream_does_not_use_b_frames -srate 22050");

Step 2.
flvtool2 is used to fix meta data from uploadedfile_temp.flv and saves it as uploadedfile.flv

exec("/usr/local/bin/flvtool2 -Uv /your/dir/uploadedfile_temp.flv /your/dir/uploadedfile.flv");