This is a build that doesn't...seem very common at all in Katarina builds. While it is AP, the start is pure consumables, but it usually ensures first blood in mid, assuming you mid which this build is intended for.

I chose Marks of Insight so that all of your abilities pack quite a punch and Death Lotus would give a lot more damage output.

Seals of Vitality were so that you aren't so easy to strike down. Sure, you're still fairly squishy, however, armor and MR seals just aren't as strong as health seals.

Glyphs of Focus because, while Kat's passive can allow her to spam her abilities like crazy, that's only if you get kills or assists, otherwise it does nothing, will allow you to shunpo for escaping more easily or throw in a few more bouncing blades.

Quintessences of Fortitude, are arguably, the best quints in the game for the early game edge they give. And as most should know, early game sets the pace for the rest of the game.

I went the common route of 9/0/21. Emphasizing on damage and CDR for Katarina while not getting any masteries that only do stuff for mana. Forced to get Perseverance over other choices because at least it does something instead of nothing for Katarina.

I start off with an Elixir of Fortitude, two sight wards, and two health pots for a few reasons.
The Elixir will give even more of an early game edge along with providing you with stronger basic attacks and a stronger bouncing blade for more powerful harassment and farming. Sight Wards because of Kat's ability to shunpo to them which can be the difference between death and a close escape. Health pots to fill the void as they, if you play smart, basically give you an extra (temporary) 200 health each.

Note: Don't activate the Elixir the instant you get it. As it only lasts four minutes you want to get a lot out of it and not waste it.

While Mejai's is a snowball item, and many would argue that's not a good item to grab ever, Katarina is a champ that can pull it off. If you still feel uncomfortable, skip it and grab Rylai's and fit Lich Bane somewhere to replace Mejai's.

Hextech Revolver is for some quick spell vamp so you can have a bit more of a survivability edge while not spending the full 3.6k~ for the gunblade while you can now focus on Banshee's and Rabadon's for more AP and survivability. Ending with the Gunblade for more damage on your abilities.

Sidenote: Make sure you always have an elixir of fortitude up after you first use one. The anti-squishiness and damage increase from that is a fairly large edge and supporting one elixir all game isn't that costly.

I focus Bouncing Blade and Killer Instincts before Shunpo. Some my wonder why I max killer instincts, which does no direct damage, before Shunpo which for Katarina is a mini-nuke. I have been able to confirm it through custom game testing. Killer Instincts passive increases the damage on EACH bounce of the bouncing blade and EACH dagger of Death Lotus. A level 5 Killer Instincts adds TWO HUNDRED AND FORTY DAMAGE to Death Lotus. That isn't small in the slightest. "But Shunpo can do so much more." Right. Shunpo into a team fight and get killed in seconds. You initiate with that and you've lost your escape assuming flash is still off CD or you don't take it.

Best Choices:
I grab Exhaust and Ignite. They help you shut down the carries and ensure kills. Exhaust can also be used to help you escape.
Other Good Choices:
Ghost, when Flash isn't enough to get you in Shunpo range. Although, if you have to Flash and they're still not in Shunpo range, you shouldn't be chasing them. Killing someone only to get killed is NOT worth it.
Flash, gives you more of an opportunity to escape/chase.
Cleanse, to stop a lot of CC, however, it won't let you be immune during Death Lotus.
Teleport, to help you get around the map where you're needed more easily.

Bad Choices:
Fortify, leave that to the tank.
Clairvoyance, leave that to the support.
Heal, not really necessary on Katarina, doesn't give a huge boost.
Smite, leave this to the jungler.

Do NOT take:
Clarity, Katarina has no mana, remember?
Rally, who uses this?
Revive, never a good option.

Pros:
INSANE damage
A reliable escape if you can play wards over walls quickly.
A nice kiting ability thanks to Rylai's.
Can pop into a fight and unleash her ult giving quick kills or assists allowing you to ult again.
Decent Farmer with Bouncing Blade and Shunpo.
Once you get Banshee's, you can ult in relative safety as it will take two hard CC's to stop you.

Cons:
Weak to CC.
Ult can be interrupted.
Mildly squishy.

As Katarina, you're more of an assassin than someone like Tryndamere who can just jump in, ult, and slaughter the everyone, spinning away as his ult nears its end. Your job is to watch from the shadows, shunpo a nearly dead target and then either shunpo away or unleash you death lotus.

It will take much practice, but you need to learn to get proficient with ward escapes. Learn to not Shunpo for initiating UNLESS you know for a fact it will assure a kill or assist, otherwise you're dead. Harass early game with Bouncing Blade. Fun Fact: If minions are nearby and not within tower range, you can run in, throw a bouncing blade at a tower hugging champ, and shunpo to a minion for a damageless tower dive.

6/10/2011 5:26 PM PST: Guide Created.
6/11/2011 1:10 AM PST: Change the item build a little as I tested out a few other ideas.
7/09/2011 1:46 AM PST: Edited guide a bit to reflect my changing playing style.

Try it before you comment, please. Will update on a ranked play section once I can test it there. (Currently I'm getting my last hitting down pat and getting more map aware and a few other things before I mess around with ranked). Any constructive criticism and feedback would be greatly appreciated.