I don't think anybody ever made that or at least was successful doing it.
Basically you need a program that extract/convert the STR from your game (check
this tools or search in google for "PSXMC", note the framerate, quality etc.. of the source and covert to uncompressed avi.
Then you need to create your subtitle and time them with the video and "burn" the subtitle in the video.
The best choise here is Subtitle Workshop (all in one) or VirtualDub with the subtitle plugin (need you to create a txt with the subtitle in the correct format separatly and use the program to "burn" the subtitle in the movie).
This are the easy steps.
Now you should use the last tool on the first link I gave you and convert back the avi2str.
The last step is to reinsert the str files into the image.
For this you need CDmage Beta 5 and remember that the sector size is 2336 is my memory doesn't betray me.
Good luck