Well, I don't karaoke but my dad does so when he comes over to visit, my PC becomes the karaoke machine.
Basically, I have a Audio Technica MB2000 microphone (any dynamic, low impedence, cardioid mic would do anyway) that I hook up to the mic input on the external breakout box of my SB Audigy Platinum eX.
For playback software, I use PowerDVD since it can separate out left and right channels. Very useful especially for those VCDs that have vocals on one channel and music on the other.
I don't record the singing, but if I wanted to I would use Cool Edit Pro. I've used it for recording audio from videos, so it should work for karaoke too - I'll just set my recording input to either analog mix or "What u Hear" and record away.

atwl