Hehe... my wife is a Karaoke addict.
Adding a mixer is easy enough. I have a Yamaha 12-channel mixer (overkill) that feeds the output of my Media PC (with Karaoke software) as well as the mics in to an unused analog audio input on my AVR (i.e. Tape in). In this fashion I can control the PC music level and mic levels independantly and send that overall mix tothe AVR for amplification.
Note that many mixers use a pro-level "+10db" signal level, and consumer AVR's are tyicall "-4dB" level. That means that you'll either need to switch the mixer to lower level output if it has sucha asetting, or be careful to limit the mixer output so as to not overdrive your AVR inputs.
However... your situation makes it sound as if you already have a dedicated Karaoke machine? If it's anything like the one that some friends gave us a while back, it came with microphones that plug directy in ot it, and it has it's own idependant mic and music volume controls, along with a master level control. If this is the case, you should be able to just pipe this in to an AVR input.
(as a side note, if you get serious about Karaoke, take a look at singsnap.com. It has a great music variety, is entirely web-based, and most of the songs are actual track music, as opposed to midi-file clones. It's $15 a month or so, but easily offsets the costs of continually buying karaoke CD's, and certainly worth it for the 10-15 hours we put in between my wife and parties each month.
Also if you go this route, you can go with much nicer mics in to your mixer than what typically comes with the karaoke machines. You'll want to get some form of reverb though...)
I know this was a lot of info, but feel free to let me know if you want clarification on anything.