I did a little bit of looking around the other day. Making Karaoke discs seems to be a somewhat obscure endeavor. I didn't find any nice help sites like vcdhelp.com or any good freeware, but I did find a couple of links to commercial Karaoke packages:
Dart Karaoke Studio got somewhat better reviews according to most sites, but in my limited testing I found it to be very unstable (on a Windows 2000 box). It locked up, threw memory access errors, suffered unhandled exceptions and otherwise crashed and burned with distressing regularity. Power Karaoke seemed to be a little bit more stable, but it didn't impress me much either.
I did manage to make a short test disc with Power Karoke and burn it in my CRW3200. The disc did work with the included CD+G player, but I don't have a real karaoke machine to test it in, and CD+G players in general seem to be amazingly rare, so I couldn't test it in any other players.