I believe you need a cd burner that is capable of burning cd-g disks, also burner software that has the abilities. As for disk type, not sure it matters. However, some players will not play cd-rw disks. Also if you are using dvd disk, it will only be playable in a dvd capable player.

BTW there is a special forum section for dealing with karaoke issues, but it's not too in-depth. But some handy links are in some threads.