MEncoder supports encoding to Sony PSP's video format, but, depending on the revision of the PSP software, the constraints may differ. You should be safe if you respect the following constraints:
Bitrate: it should not exceed 1500kbps, however, past versions supported pretty much any bitrate as long as the header claimed it was not too high.
Dimensions: the width and height of the PSP video should be multiples of 16, and the product width * height must be <= 64000. Under some circumstances, it may be possible for the PSP to play higher resolutions.
Audio: its samplerate should be 24kHz for MPEG-4 videos, and 48kHz for H.264.
Example 6.4. encode for PSP
mencoder -ofps 30000/1001 -af lavcresample=24000 -vf harddup -oac lavc \ -ovc lavc -lavcopts aglobal=1:vglobal=1:vcodec=mpeg4:acodec=libfaac \ -of lavf -lavfopts format=psp \
Note that you can set the title of the video with