I am looking for software to turn MP3 and CD+G into an MP4, MOV, AVI, or any other common video format.
Sound Design Stack Exchange is a question and answer site for sound engineers, producers, editors, and enthusiasts. It only takes a minute to sign up.Sign up to join this community
You could use CDG Ripper to rip your CD: http://www.tricerasoft.com/karaoke_software/CDG_Ripper_Extraction_Tool.html
Then you could just use Pinnacle Studio, Vegas Pro, Premiere, (probably) Windows Movie Maker or whatever video program you like best to combine them.