From what I know,Format should be mp4, container codec should be MPEG4, ideal resolution is 320x240 (16:9), though not standard resolutions can be used (if you have modded firmware). Any bitrate will work which is <1500.
But, most of the video converts will have the profile for PSP, i think.