Of course, getting to that point was more than a little painful. It seems that the whole process is spottily documented (at best). In the end, I did manage to make it work on my system. While this won't work for everybody (since it's written for Ubuntu 10.10), hopefully it will help out somewhat.
- Install bc and mpeg4ip-server (for the command mp4creator). These packages come from Ubuntu's standard repositories.
- Install mplayer from Medibuntu
- Download this script (syntax highlighted version here) into a file named /usr/local/bin/androidmp4 and make that script executable
Now, you can simply run "androidmp4 video_file_name", and wait. You will be given a file that can be played on at least your PS3 and the Samsung Galaxy S series of phones.