For this video, I used a program called "Aegisub". - It lets you create stylized subs. So, I made them look like the one in Shenmue (but not exactly, it's actually the font of Shenmue II's loading screen, but with colors and shadow, to make it look like Shenmue's text and sub, and match who's talking on the screen).
Then I used another program called VirtualDub. What this program does is to burn the subs in the source file. That means the subs doesn't come as a separate file, but they are burned in directly to the source video file. - The caveat with this is that it exports the video as an AVI file (there are workarounds to make it export as MP4, but they need time to be set).
However, this was not much of problem. I exported it as an AVI (without compression, for the best quality). The funny thing is that it produced an 21GB file... Therefore, then I opened this file with Camstasia Studio and finally produced an MP4 file (YouTube process MP4 files faster).