Not Updated For Current Season
Many people say that my build is somewhat odd for a Katarina, but let me go ahead and say that I generally get a 10ish to 1 kill/death with her, and many assists. If you play katarina to her strengths, you really are able to shine with her while gaining stacks on her Mejai's/Sword of the Occult.
You really shouldn't have any trouble gaining stacks, but on the offchance you are, it isn't that huge of a loss to trade either/both in on something like a void staff.
When you enter your lane, try to play it safe to some degree, using shunpo/bouncing blades to snag creep kills every time they come off cooldown. I generally recommend going middle lane, because you can typically snag an early kill of their carry, sending you well on your way to owning, and delaying their development some so you can eat them all game long. Be careful you don't shunpo yourself into range of a powerful early game poker. You do have three health potions, so you can sustain some of this, but you don't want to continue doing it.
Many games I am able to get my first kill by level 4 using a combination of their harassment aggressiveness and bouncing blades to poke them down to low hp, then Shunpo/Blades/Exhaust/Shunpo/Blades(If necessary) for the kill. Be sure you don't initiate this combo until they are close to your tower, as you obviously won't have the time needed to chase them into their tower.
Many people question my choice of taking Teleport on Katarina. She isn't really a pusher, so why bother? Well, with early boots/shunpo you shouldn't be getting killed by anything early game so you don't need any of the escape abilities, and you don't need flash to initiate. What you do need is an early game advantage. So at approximately level 6-7 I continue to poke the enemy squishy down to about half health, when I've killed enough creeps, I pill back to base and buy my mejais, then teleport back to a creep just shy of my tower. Generally they don't worry about withdrawing when they see you pill back, so they'll approach your tower somewhat. You can then initiate with your Shunpo, blade them, exhaust, and then ultimate a little behind them for maximum effect. Sometimes, depending on the hero and build, you have to shunpo them again, but this is rare. Bam, two stacks. Continue to farm a little bit until you can afford at tome or even your sword of the occult, then let the farming begin!
If you did this right, and have a few stacks on your mejai's or even your sword as well, ganking should be easy from this point on. Just shunpo into the enemy squishy, preferabbly with a teammate standing by to stun or slow, and then pop your blades/ultimate. They should all fall like dominoes. Remember to play it safe to preserve your stacks and buy that giant belt out of order from the Rylai's to get you that extra survivability.
You know the drill, and by now you've probably got 20 stacks on both snowballs, or close to it, Carry on killing. Usually by the time this build completes you're looking at 500-600 damage blades, 500-600 damage shunpo, and your ult just tears everything apart.