It's the same as making a website for a mobile phone and making ringtones to download.
Two issues I see over and over, and maybe one of them is yours...
(1) MIME Types
Depending on where the file is hosted, the problem could be that you don't have MIME types setup. Cell phones use mp4 as well, but if you don't setup the MIME type on the server, it will display the "code" as you say. So, if you are sure MIME types are setup correctly on the server for the PSP, go to problem #2.
(2) Descriptor Files
Usually a link can not be directed DIRECTLY to the mp4 file. For example, on a PC, if you click http://domain.com/test.mp4 it would stream the file, if you right-click save as, you would save the file, but on cell phones (and Im sure PSP's) you need one extra file called a descriptor file. So for example you would click the link on your PSP, and it would go to http://domain.com/test.EXT (EXT=whatever the descriptor file extension is for PSP, for cell phones its GCD), and on the file.EXT, which contains size, name, path, and other variables, it will then automatically link to the mp4, making it able to download the file.
Some cell phones, and I don't know about PSP, have to have the actual media in a certain format. For example although it's mp4, maybe your frame rate has to be at a certain count per second on order to make it even viewable, but I think that's more of an issue with cell phones rather than PSP's.
Hope this helps.