Ah, that's a little trickier.
For 2.X PSPs, it'll go into one of those funny named folders in the root, AV or MV10something.
For 3.0 and up it's the X:/VIDEO folder.
The only format that I'm aware of working is mp4. (Someone feel free to correct me, though.)
Tck, I just thought of something. If you format the memstick using the PSP, it'll make all of the necessary folders for you.