I've actually done this, although not to videotape, but in order to overlay subtitles on anime videos when showing them. I'd be willing to provide a walkthrough of the process.

I'm doing it too.
And there are no secrets involved at all.

The Amiga software was called "Jacosub" iirc.
The (mostly used) Windows software was called SubStationAlpha.
Other programs existed back then, which had their own script formats.
Converters were available for most popular script formats to be converted
to be used with other programs, even on other platforms.

For genlocks, probably standard stuff was Multigen/Deltascan, anything from VineGen.
It basically works like this:
Record audio from LD -> time subtitles to audio -> Translate ->
fine tune stuff (like text events, scene bleeding etc) -> after
several hours (or days of work) the script is done.
Connect genlock to the computer (via VGA/RGB) -> connect video out from LD Player to genlock ->
connect genlock video out to vcr video in -> put subtitling software into "play" mode -> have it all sync perfectly ->
record master tape with fansubtitles -> copy master tape and send it off -> done

What the genlock does, very basically said, it mixes the incoming video with the video from the computer:
And the video coming from the computer is a black screen displaying only the subtitles nothing else.
And the genlock ignores the black screen and only takes the subtitles (which cannot be black, but any
other color) and imposes them over the picture from the incoming video source, i.e. the LaserDisc.
What you end up with, if you have a good script, is a perfectly subtitled LD.
You can also apply this without recording anything, like if you want to watch your japanese LD's with
subtitles, which is what I have been doing for some time now. The genlock I use is the Coriogen Eclipse.

http://www.pustan.com/test/k_coriogen.jpg
This is what the genlock looks like

http://www.pustan.com/test/k_ssa.jpg
Subtitling software looks like this (SSA in edit mode)

http://www.pustan.com/test/k_subs.jpg
And the subtitles look like this.
But you can use any color, font, size you like really.
Most important thing is the timing.

I was actually going to try connecting a genlock, but somehow I got lost. I still got the stuff to resume one day. But it seem where it stopped where actually to find subs for the lds ? Not many seemed eager to share them anymore. But maybe its just me not knowing where to look.