This can be done fairly easily.

First download virtualdub and the subtitler plugin. (links below)
http://prdownloads.sourceforge.net/v...1.zip?download
http://www.virtualdub.org/downloads/subtitler-2_4.zip

Extract both of these to a folder and run VirtualDubMod.exe.

In File > Open Video File...
Select the video you wish to edit (.avi).

Next, go to Video > Filters...
Here go Add... and then Load...

In this screen go to where you extracted the Subtitler.vdf file, select it and press open.

You should now be able to choose Subtitler from the list of filters.
Once it is selected press Ok.

In this screen press the ... button and select the .ssa file.

After this you can save your new .avi file that has the subtitles attached.(File > Save as...) Here you can set which codec you wish to compress the file with but it is not necessary (this file may be large if you do not use compression though). This step will take awhile, as the program build a new video file.

I believe there is a way to get virutaldub to correctly encode your video file, but I usually use another program to do this.

The easiest way (or one of the easiest ways) that I use to get videos in PSP format is PSP Video 9. (http://www.pspvideo9.com/)

Once installed, you simply go to the convert tab, press Transcode New Video, select the video you wish to put on your psp and press start.

All that should be left after this is transferring the file!

Hope this helps.