One of the features not advertised by Sony, but widely advertised by PSP users/enthusiasts, is the ability to convert video files to a format which the PSP likes for watching on the go. I've scoured the Internet looking for "How would I convert videos for the PSP with one of my Linux machines?" - only to be skunked every time.
However, with all the tools for Mac OS X and Windows, I discovered a common theme. EVERY ONE was using FFmpeg. EVERY ONE. Well hey, FFmpeg was developed on Linux in the first place, right? How hard can this be?
Thats from the tutorial at this site --> http://www.linuxpspvideo.org/