All you need is an S-Video connector and some ribbon cable.
1. Open your N64.
2. Remove all the screws that hold the board in, which is pretty much all of them.
3. Solder 4 wires to Luminance, Luminance Ground, Chroma, and Chroma Ground, as shown in the picture below.
4. Find the pinout of your S-Video connector. I.E., figure out which pins on the bottom go to which holes on the top.
5. Solder Luminance, Luminance Ground, Chroma, and Chroma Ground to the appropriate connectors on your plug.
6. Remove a bit of plastic on the side of the case to make room for the connector.
7. Attach it with plenty of hot glue.
8. Reassemble N64.
See the first picture for help. After that you can see finished photos and a picture comparison.

Here is the finished product:



Here it is compared to composite:
S-Video:

Composite:



