You can add the impress news
http://www.watch.impress.co.jp/av/docs/20041215/nintendo.htm
The interface is simply horrible.
DARK ANDY said:
I don't even know how you will be able to watch Movies with a memory stick...
http://www.memorystick.com/psp/manual/000001/00.html
here is the manual

the program must be purchased though (1000 yens)
Since it is standard H264 , you can encode with whatever you want if you don t want to purchase this, you just have to follow the folder and naming conventions for PSP (a bit tricky, i don t remember where i saw it, basically it s replicating sony video camera save behaviour).
I ve seen a How to Do on either gamespot or ign i can t remember :P
edit: it was gamespot
Q: How do you get the PSP to recognize video files?
A: While formatting a memory stick in the PSP creates folders for audio files, game saves, and actual games themselves, there's no clear path for placing video on the unit. The system supports a specific flavor of mpeg-4 for its video, so you'll need something capable of encoding or transcoding to that format. Sony is supposed to release a downloadable version of its video transcoding software, Image Converter 2, to handle this, but as of yet, we haven't been able to find it. A third party has developed a freely available program called 3GP Converter that will also manage this process. But getting the files into the proper MP4 format is just the beginning.
The PSP reads video files using a directory structure that isn't put on the stick when you initially format it for PSP use. So you'll need to create a root directory called "mp_root" first, then place another directory named "100mnv01" under it. You put your MP4s inside that directory, but they must be named a certain way for the PSP to recognize them. The naming convention is m4vXXXXX.mp4, where "XXXXX" is a series of numbers, such as, say, 00001. Once you've jumped through these hoops--and it's really only a hassle the first time you do it--you'll be watching your own videos on a PSP. Why is it like that, you might ask? We're guessing that it's the same file structure that Sony's video recording memory stick devices use.