Basically, KC wants density of Actions, and particularly Actions which give +$2 or more, +2 cards or more, or virtually anything which gives you a choice on the card. Or curse-giving attacks. Non-terminal card drawers with KC are amazing, since you'll actually be able to use what you draw, and particularly they set up KC-KC rounds.
So, KC-Lab: wonderful. +6 cards and you'll be able to use all the cards you draw.
KC-Village: Unexciting. You just barely end up with a card advantage (use two cards to draw 3 cards), and you probably don't need 6 Actions.
KC on a terminal which gives +$2 (like Militia or Chancellor or even Woodcutter) isn't exactly thrilling, but it sets you up to buy more KCs, since you get $6 out of it.
I think that a common trap that I fall into is that I have pursued a big-money-ish strategy to get up to the point where I can generate $7, and then I'll draw KC dead more often than not. If you're going to go KC, you want a deck that can benefit from it as soon as you get your first $7.
KC-Pawn and KC-Steward are surprisingly good. KC-Minion is unsurprisingly good. The ability to tune your second and third plays of the cards to respond to what happened with the first play is key.
KC-KC is amazing with almost literally anything, as long as it isn't dead.
So, um, in summary:
You'll want some kind of card drawing (or aggressive early trashing) to get to those first few KCs you draw, and because KC-card drawer is solidly good at worst.
You'll want the minimum necessary Treasure to build to the point where you can somewhat reliably buy KCs.
You'll want Actions that produce Cards, Money, or produce Curses to play the KC with. Having them be non-terminal is nice, particularly with +cards. Having them be Villages is usually not good.
Cards that are usually mediocre when played with KC
1. Trashers, though there are exceptions.
2. Village-type cards.
3. Things which produce $1 or give you +1 Card.
4. Attacks which do not have a cumulative affect when played multiple times (though almost all such attacks give you +$2 or +2 Cards, so they aren't AWFUL).
5. TREASURE (obviously, and of course it isn't really played with KC).