Hiya! After about a hundred games of Katarina, I decided to write a new guide on how I play Katarina. Katarina is one of the most deadliest champions if fed and snowballs epically fast. Her Shunpo is an unbelievably strong nuke at a very low cool down and her Ultimate, Death Lotus, can complete destroy a whole team. However, to utilize Katarina to her full potential you must play smart, have good positioning and farm quite a bit. Being an assassin, Katarina kills like a boss.
Disclaimer: I would like to say I do not consider myself the best Katarina player, nor that this is the best build. This is just how I play Katarina. And I have been quite successful.

As a militaristic state, it would perhaps come as no surprise that the primary responsibilities of Noxian women are raising strong children and providing succor for husbands who walk the path of soldiery. There are some, however, for whom nurture is not nature, and Katarina is just such a creature. Born the daughter of the feared Noxian General Du Couteau, the girl was always more interested in her father's knives than in the dresses, jewelry, and other trifles that her sisters spent so much time fussing over. A childhood dispute soon unveiled her uncanny knack for bloodshed, and her father, ever the opportunist, happily fostered her killer instincts. After training under the tutelage of the finest assassins the mighty city-state had to offer, Katarina first cut her teeth performing assassinations in the Ionian War. There, her ruthless mastery of the knife and dagger combined with her sadistic temperament to earn her the title Sinister Blade, a moniker that would follow her for the remainder of her career. She is most famous, however, for her exploits in the campaigns against Demacia, especially those surrounding her engagements with the nation's champion, Garen; a rivalry that began when she recovered the remains of Sion from a vanguard under his protection.

With the demand for warfare somewhat arrested by the tenuous peace settling over Valoran, Katarina sought the allure of violence in its last remaining haven: The League of Legends. Some might say it was an inevitability that Katarina's chosen path would draw her to become a champion of the League, continuing to enforce the will of Noxus and bring prestige of war to her noble family. There, she continues to perform her bloody work - esteemed and reviled, feared and adored.

''The Sinister Blade of Noxus is like a black widow - beautiful, but deadly.'' - Garen, the Might of Demacia, following a skirmish in the field

Pros
Massive damage
Can attack multiple enemies at once with Death Lotus
Built in escape/chase with Shunpo
No Mana [spam them abilities!]
Epic Passive

Cons
Squishy
Focused
Bad early game
Shut down by CC

Greater Mark of Magic Penetration
Greater Seal of Armor
Greater Glyph of Scaling Ability Power
Greater Quintessence of Scaling Ability Power
Runes are pretty standard for any AP Caster.
Magic Pen Marks are the best, no contest.
I use Armor seals for a little bit of survivability early on.
AP/lvl Glyphs and AP Quints help her to hit like a truck.

After mastery remake, 21/9 is just great. Offense Op. 9 in Defense for trading. 21/0/9 could work if you want the movement speed.

Flash
Ignite
Exhaust
For summoner spells, I pick up Flash and Ignite. Now I know some of you will go "WE HAZ SHUNPO! NO NED FLASH! STUPID! DOWNVOTE!". But many times you won't have a target to Shunpo too and every death hurts your stacks. Ignite is taken for the extra burst and helps with those early kills. Exhaust is also plausible and helps your ability to 1v1 and keep them in your ult. I used to take this for the slow, but I realised that after Rylai's, it was pretty unnecessary.

Death Lotus > Bouncing Blades Shunpo > Preparation
I prioritize leveling up Q until Level 6, grabbing a point in W and E. This is because Q is much better at harassment and last hitting. After level 6, I focus on maxing Shunpo as it is the strongest of Katarina's abilities [aside from her ultimate]. After E, max out Q. W is leveled last as it doesn't increase Katarina's DPS in any way and one point in W is enough for a while. And of course add into R whenever possible.

Boots+ Health Potion
Hextech Revolver
Mejai's Soulstealer
Mercury's Treads
Sorcerer's Shoes
Rylai's Crystal Scepter
Rabadon's Deathcap
Will of the Ancients
Void Staff
Zhonya's Hourglass
Abyssal Mask
Quicksilver Sash
Boots + Health Potions help your early game as the 3 Health pots help you sustain your considerably weak early game and give you some movement.
I get a Hextech Revolver to help her survivability a bit more and for the small AP.
Mejai's is a necessity. Keeping those stacks up gives a massive AP boost and being Katarina picking up stacks are quite easy.
Level 2 Boots are quite situa]tional. Most of the time, the team will probably have a lot of CC and Merc Treads are your best bet. IF they have 2 or less CC then Sorc Shoes are a good choice for the Spell Pen.
Rylai's next as it is just awesome on Katarina, with the awesome Slow on your skills and the nice amount of AP and Health. Nobody can run from your death lotus anymore!
Deathcap for a huge AP boost, the 140 AP and the 130% adds a ton of AP.
Finally we build our Hextech Revlver to a Will of Ancients for the Spell Vamp and nice amount of AP.
Your last item is always situational.
If they are stacking Magic Resist, you can get a Void Staff.
If you want some AP and surviabiltity, Zhonya's or Abyssal Scepter is just great.
If you find that CC is killing you, Banshee's Veil or Quicksilver Sash is for you.

It would be best to have a solo lane so that you could get your ultimate as fast as possible, but Katarina works well in a bot lane too [especially if paired with someone with a stun or hard disable]. Leveling Q helps with Last hitting and harassing as Katarina struggles early on. Play carefully and spam that Q for harassment and last hitting. I tend to play very passive until level 6 and then quickly go aggressive at 6. They usually don't expect you to suddenly become so agressive and usually it will lead to a kill or two.

Using Katarina's skills properly is helpful.

For single harassment:
Q [enemy] -> W -> E [enemy] is pretty standard. Throw a blade then Shunpo in with a nice amount of dmg reduction.
If they are much stronger than you in lane:
Q [enemy] -> E [minion] is good. Throw a blade and then gtfo with a Shunpo.
To kill them, the normal skill sequence is:
Q [enemy] -> W -> E [enemy] -> R -> Ignite

After seeing a few very bad Katarinas I felt the need to write a section about Death Lotus.
Death Lotus This is your bread and butter after level 6. Your usage of Death Lotus can easily make or break a teamfight. So here are a few tips.

Firstly, Never Ever EVER initiate a fight with Death Lotus. Hell, you shouldn't be initiating at all. Secondly, if they haven't used a single CC, don't Death Lotus. Don't. You will get interrupted and then raped. Thirdly, just a reminder, Death Lotus REQUIRES you to be in a VERY bad position for a squishy. Right in the middle of the fight. So be careful when to use it. The BEST time to use Death Lotus is when an enemy is disabled [stun, fear, taunt, any hard cc]. A Sion stun + RQWE is almost always a kill. If you have a team with CC, WAIT FOR THEM TO CC. Don't jump in and ult and scare them off before Sion can stun.

So the summary is:
1) Don't initiate. EVER.
2) Don't ult when the enemy still has a lot of CC
3) Be smart. Don't kill yourself by being in a bad position thinking you can 1v5
4) Wait for your team to CC.

The "Free Flash" trick is simple. Take a ward. Place the ward and then shunpo to it. Best through a wall for a quick escape/chase when flash is on cd. This takes some skill and getting used to, but once you get this down, you get free flashes!

Also make sure to use W before using Shunpo. Why? Because that dmg reduction is much better than the heal reduction most of the time [unless it's like a Mundo or Soraka or something of that sort and even then we have ignite].

Here I will try to give a few tips on laning against some popular solo laners. I'll add on to this...

Color
Red indicates a hard matchup. I suggest to switch with top.
Yellow indicates a medium matchup. Whoever plays better wins.
Green indicates an easy matchup. Winning is easy.

Ashe
Pretty easy laning. Squishy as hell. Your harassment can take away a nice chunk of health. Her slow is annoying so it might be a good idea to do Harassment 2 [Q->E] Can easily beat her in lane from 1-6. If her Volley is a problem, stay behind minions. Keep harassing. Once you hit level 6, if you have been harassing, you can kill Ashe in seconds. The only problem is her Ultimate as it interrupts your ultimate. A nice idea is to Shunpo in and NOT ult. Some players panic against Katarina and ult right away. If Ashe isn't careful and doesn't panic, you can probably ult and kill her before she can even ult in time.

Annie
Her QW Harrass is very strong. Stuns and her Flash -> Tibbers just rapes you and your squishiness. Hard to lane against and even after you get your ultimate she can interrupt it with hers. Keep track of her stuns and harass properly, without taking too much harass back, and you can win.

Corki
Farms like a boss. Thankfully laning isn't too hard. Harassing shouldn't be too hard. Once you get to level 6, it's still quite even. Even though he can't INTERRUPT your ult he can ESCAPE. His built in flash can be a real ***** and can easily get out of your ult with it. And those missiles have huge range. Don't expect easy kills, even with his squishiness. At the same time, if he tries to kill you, you can turn on him and get a kill pretty easily.

Caitlyn
Pretty tough laning until level 6. Her range is a ***** and she'll spam that Q hard. Try to sneak in some harassment. But it won't be easy as she outranges you. The great thing is once you guys hit level 6. Caitlyn is super squishy and has NO means of interrupting your ultimate. Once you hit level 6, the sides turn in your favor. If Caitlyn doesn't have VERY good positioning, killing shouldn't be very difficult.

Ezreal
Very dependant on 2 things. His skill level. And yours. IF he lands those skill shots you are gonna have a hard time. To land it he must be half decent, and you must be trying to NOT dodge it. But overall he's pretty squishy and you can max E ASAP. Sadly, he has an easy escape from your ultimate, so it's best to attack after he uses his Essence Flux and never ult when he has it up.

Fiddlesticks
You won't see too many people playing him. Overall, he can be a pain with his constant silence, and his Fear is quite scary along with his Drain, making harrassing dangerous. He's hard to kill with his constant sustain+damage by Bountiful Harvest. He's pretty squishy by nature, and his silence is on a quite long cd, so it shouldn't be impossible. At Level 6, both of you will get really strong ultimates. It'll be a matter of who outplays who, but it'll be a bit in favor for Fiddlesticks.

Jax
Edit: After remake, I think it's very easy to beat Jax. He isn't quite as tanky as he was and harassing/trading is very easy now. Max E first, harass, and at level 6 you can grab kills.

Kassadin
Nightmare. Lane Switch is best idea. If you must, Max Q and play defensively getting last hits with Q.

Kog'Maw
Squishy. No interrupt for your ult. And no escapes! Like Caitlyn, his range is a real pain and it could be difficult to lane against until your shunpo is levelled up a bit more. Sneaking in some Q shots with [Q -> E] isn't too hard though.

LeBlanc
That silence. That harass+burst. Lane switch ASAP. You will get murdered easily. Not much else to say...

Lux
Really easy. Squishy. Mild harass. Can't interrupt your ult. Just an easy lane in general. Up to Level 6 try to dodge her snare and skill shots. It shouldn't be too hard to harass her. Basically every time she uses her spells, E into her. At level 6, a QWER should be able to net a kill.

Overall, you will have a hard time against people who can constantly disable you and interrupt your ult and people who are very tanky. Such as these guys:
Alistar Amumu Annie Blitzcrank Cho'Gath Fiddlesticks Janna Jarvan IV Kassadin LeBlanc Kennen Poppy Rammus

Katarina's role in teamfight is simple.
Spam your Bouncing Blades and when the time is right Shunpo in and ult and murder their team. Take every kill/assist you can get as your passive may even allow you to ult twice in one fight and also get them stacks! It's best to wait and come in later after their CC have all been used. If you can come in when all their CC is used, then it's normally an easy double or triple kill and teamfight victory.

While Katarina is often considered a pubstomper and only good at "low elo", I believe she adds a lot of dps and can be a good addition to any team whther it be low elo, high elo, normal or ranked. The damage Katarina can do is enormous, but to maximize it you must play smart and get a lot of kills. And to get these kills sometimes you may have to "ks" [kill secure :P] which may lead to your team being slightly "irritated" [NOOB KS!!WTF!]. But in the end, if you get 20 stacks and finish your build, you can probably 1v5 and come out on top. Thanks for reading the whole guide! Leave your comments below.

If you follow the guide it'll look something like this:

08.16.2011 Guide Created
08.17.2011 Minor changes
03.16.2012 Changed masteries. Minor Changes.
03.16.2012 Updates Lane Matchups. Not too many Ashe or Corki or Malzahar Mid anymore :(