If you are looking for GPL'ed stuff:
For audio mucking about, try sox. Very powerful! It does a lot! It's included in most linux distributions.
There is also the famous LAME for mp3 [audio] encoding.
For video, mencoder is impressive! It's part of the mplayer package. It will handle conversions from most video formats. Far more than I ever dreamed existed. (For documentation, see Chapter 9. Basic usage of MEncoder and Chapter 10. Encoding with MEncoder.)
It's somewhat more limited about what it can create. But it does support mpeg4, mpeg2, dvd-mpeg, flv, and many others. (While I haven't tried flv myself, google shows other folks are using it.)
I have done things like jpeg + sound -> mpeg4 movie:
nice +20 $MENCODER mf://${JPEGFILE} -mf w=720:h=480:fps=1/${SOUNDLENGTH}:type=jpeg -audiofile ${SOUNDFILE} -ovc lavc -oac lavc -lavcopts vcodec=mpeg4 -ofps 30000/1001 -o ${MENU_MPG}
Or transcode arbitrarily formated video to dvd-compatible mpeg:
nice +20 $MENCODER -edl ${EDL} -ovc lavc -oac lavc -lavcopts vcodec=mpeg2video:vrc_buf_size=1835:vrc_maxrate=9800:vbitrate=${VBITRATE}:keyint=18:acodec=ac3:abitrate=192:aspect=4/3:trell:mbd=2:dia=4:cmp=3:precmp=3:ildctcmp=3:subcmp=3:mbcmp=3:cbp:mv0:dc=10 -of mpeg -mpegopts format=dvd -vf scale=720:480,harddup -srate 48000 -af lavcresample=48000 -ofps 30000/1001 -o ./${INFILE}.reformatted ${FILEPATH}
-edl/-edlout [Edit Decision Lists] are used to snip out just the video sections I want.
${VBITRATE} is normally 5000 for DVD-mpeg-video. But if you flub it a bit you can squeeze more video onto a dvd. Assuming you can tolerate the artifacts.
scale=720:480,harddup -- Little issue with the scale being wrong for my dvdplayer, and harddup to resolve a sound-video desync issue on my "el cheapo" player.
(To playback on a widescreen player that wouldn't handle 4x3 video, I've used atrocities like "aspect=16/9", "-vf scale=560:480,expand=720:480,harddup". But in general you don't want to waste bits encoding black-bars.)
This is not the most efficient set of options to mencoder by far! It can be time consuming to run. But I had other goals in mind...