Moth3r said:
Add the subs, then add simulated grain (from a filter such as GrainFactory3) using a transparency mask so that the grain is only applied over the subtitle text.
I'd vote for this option. The first sounds too destructive to the picture for my tastes.
I'd also, as has been said, recommend softening the subtitles a bit (add a pixel or two blur to it) in order to blend it in with the softer picture.