1. Katarina's Role, and Pros and Cons

Playing as Katarina, you have 1 major goal; kill people. You are not a tank. You are not a pusher. You are not a support. You are an assassin and a mage, and thus, killing other mages and assassins is the job you want to fulfill. 

How to implement your role

The most basic, important gameplay aspect of Katarina is setting up your ultimate correctly. Katarina is very much based around her ultimate, since it's a low cooldown, high damage ability that can absolutely devastate a team fight if used correctly. Killer Instincts' active effect used with Shunpo is exactly what you need to set up that ability.

Pros and Cons to Using Kat

I personally love playing Katarina. That's why she's one of my most played characters and why even if there are a lot of negatives to her, she's a very fun champion once you get the hang of her and can dish out massive damage.

Pros:

*Fun, intuitive playstyle unique to Katarina
*Able to deal massive damage to several targets
*Passive allows her to kill people with her ultimate even if she's already used it once in a team fight
*Solid champion all the way through the game
*Able to close the distance between her and a squishy very quickly and effectively
*Has no mana, so has enormous staying power
*Is an anti-caster and an anti-healer due to her Q applying Grievous Wound
*Hawt body and a sexy voice, need I say more?

Cons:

*Very squishy once her KI-SP buff is down
*Has to be in close range of targets for her ultimate to work, putting her right into the fray and increasing her chance of being focused
*Ultimate is interruptable
*Easily countered by any team with 2+ stuns or heavy melee burst
*Can not out-burst Ezreal, a very common midlaner
*BF swords are expensive and thus she doesn't get very effective until mid-game unless you go AP

2. Pre-Game: Runes, Masteries and Summoner Spells

In my opinion (and this is solely in my opinion) there is really only one way to build Kat's runes/masteries.

Runes Breakdown:
As far as Runes go, you want to be stacking Flat Magic Penetration reds, Flat Dodge yellows, Flat CDR blues. Quints are kind of up to choice. I like 2 flat HP and 1 movement speed for first blood capabilities, if you're really concerned about them stacking Magic Resistance you can go for a Magic Pen quint or two.

Masteries: 21/9/0. No exceptions. You are an assassin. That means you need to deal your damage quickly and get out. If someone focuses you, bam. You dodge them, have 10% increased movement speed on top of shunpo and you're out after getting a couple kills.

Mastery Breakdown:

Offense Tree:
3/3 Deadliness
1/1 Cripple
4/4 Sorcery
1/4 Alacrity
1/1 Burning Embers
1/1 Archaic Knowledge
3/3 Sunder
3/3 Brute Force
3/3 Lethality
1/1 Havoc

Defensive Tree:
3/3 Resistance
1/3 Hardiness
4/4 Evasion
1/1 Nimbleness

Summoner Spells Breakdown

My summoner spells of choice are Ignite and Exhaust. This is a ganking combination and you're going to be netting a lot of kills.

To review the other skills;

Revive: Just no.
Heal: When the hell do you need to heal? You're getting kills and getting out. Waste of a slot.
Clarity: Well, you don't have mana, so..
Fortify: Great spell for a support class. You are not a support class.
Clairvoyance: Again; great spell for a support class, or a tank. You are neither.
Flash: I usually never have a situation where this would help me escape better than Shunpo would. Wards and juking with Shunpo render this useless for you.
Ghost: Shunpo is definitely good enough to catch up with someone, and to run away if necessary.
Rally: Great spell for a tank. You are not one.
Smite: Wtf?
Teleport: Unnecessary and has a long cooldown. Just not something for Kat.
Ignite: Nets you kills. What more could you want?
Exhaust: Helps you to get away or get kills. Perfection.

3. Skills and Their Order

Katarina's Skills

Passive: Voracity. 

-On champion kill or assist, rewards 25g and knocks 15 seconds off of all your cooldowns. This is hands down one of the best passives in the game, particularly for the kind of character Kat is. Since her ultimate does so much damage she can frequently land multi kills, or at least get a few assists in a team fight. Her ult is on a very short cooldown, and a triple kill with her ulti would mean that she can instantly use her ulti again to mop up the other champions. This is sick as hell and has actually gotten me a couple penta kills.

Q: Bouncing Blades.

-Katarina throws a dagger which bounces between targets. Rank 1 bounces between 2, 2 between 3, 3 between 4, etc. This ability is a decent nuke, but what's truly great about this skill, besides its wonderful harassment since you don't have to worry about mana, is that combined with Killer Instincts, it's a bouncing grievous wound debuff on a short cooldown. That means that basically you are an anti-healer. You can keep their healing at 50% constantly. It also means Mundo won't be able to do much regenerating. In addition to the uses I've already listed, this ability is great in combination with Shunpo for an early-game kill. W-Q-E-R combo often nets me first blood. Furthermore, it's great for mopping up after a team fight. It's fun to get a double kill in a team fight, then hit BB on the 2 at low health running away and score another double, or a quadra, depending on timing.

W: Killer Instincts.

-Katarina's melee attack damage is passively increased. In addition, she can activate this ability to buff her next Q or E. The passive on this is meh. However, the active synchronizes perfectly with her other abilities. This can either apply a grievous wound debuff to several enemies with your Q or it can reduce damage dealt to you by a generous amount for 3 seconds with your E. Either one of these actives works perfectly with your combo and the ability altogether is just so delicious. You don't need a lot of points in this to be effective though, since the active doesn't change much throughout the levels, so it's pretty low priority after you get 1 or 2 points in it.

E: Shunpo.

-Katarina teleports to target. If it's an enemy, she deals damage. This ability is one of my favorites out of any ability in the game. Why? It's a free flash with a nuke on a low cooldown that allows me to either port to an ally as a getaway, juke someone completely with a well-placed ward, mop up after a team fight or get early game kills. Yes, please. This in combination with W is what you're going to be using to set up your ultimate most of the time. Since her ultimate's range is so short she needs to be right in the fray in order to deal damage with it, so this helps her line up 3 targets around her to destroy. W ensures you don't die as soon as you port in. It's a win-win scenario.

R: Death Lotus.

-Katarina spins in a circle, hurling daggers with unparalleled speed at enemy champions, 1 champ at rank 1, 2 champs at rank 2 and 3 champs at rank 3. This ability is DELICIOUS- except for one problem. It's a channeled ability. It deals massive damage to up to 3 champions at max rank. This is what makes your opponents go "oh, ****." when they realize that they're up against you and they have next to no CC, because you will kill all of them with this if they don't stun you in the middle of it. As I've already mentioned, though, it's a channeled ability. Thus, it can be interrupted by stuns or silences. It sucks to be interrupted since no matter if Kat is AP or AD, she's pretty reliant on her ultimate to dish out heavy damage quickly. This is still a very strong ability and a great asset to team fights, though, particularly in coherence with a good Galio.

Skill Order

My skill order is actually pretty relative to who I'm playing against. However, since I usually play mid when I'm playing as kat, I go:

Q-E-W-Q-Q-R

After that, R>Q>E>W. This is a little bit unconventional but I find that it works very well.

Now we come to the topic that encompasses 99% of the Kat threads on these forums.

4. Item Builds, and the AP vs. AD Conundrum

Building Kat is a tricky thing. Why? Simple. Her abilities benefit from both Attack Damage benefits and Ability Power benefits. Bouncing Blade benefits solely from AD, while Shunpo only gets +damage from AP. Her ultimate is roughly the same damage, though it scales a little better with AD. 

There are a lot of arguments as to whether AP or AD is a better build. I think that they're both viable options and really it comes down to personal taste. They're totally different playstyles.'

AP relies entirely on your ultimate. Therein lies its flaw; if a team sees you hit DL, they silence/stun you and you're worthless for the rest of the fight. You are, by every definition, a one-trick pony as AP. Shunpo does some decent damage, but your auto-attacks are worthless and unless you're building lich bane (not part of your core build) you're going to be doing zero damage after shunpo is down. However, because you have Rylai's, your ultimate is easier to get off, and you have more health given to you from this build than AD gives. AP is better in say, unranked, since people aren't coordinated and aren't CCing reliably. I play this build more often just because.. well, it's easy. And if they don't have CC, you will dominate the match.

AD, on the other hand, relies less on your ultimate because BB and auto-attacks still do nice damage. There are problems with this build, too, though. For instance; in order to make this build effective you really have to build a glass cannon. Like 2000 health glass cannon. That's fine really since you can kill them before they have a chance to touch you, but still. You are squishy as ****. Your core build doesn't give you any HP and straying off your core build is expensive. Also, before you get your first BF sword, your damage output is low, because your core items are spendy and don't have a lot of buildup. This build is much better against CC-heavy teams since you have a decent source of damage after your ult is down, and 9 times out of 10 people in ranked play will know to CC you when DL is happening, so this is more viable in ranked queue in my opinion. I've heard a coordinated AP can outperform AD, but I've never seen it in action.

Alright, so now we come to the big, important part.

Item Builds.

Now when I give you these builds keep in mind that they are situational and by no means should you only ever build these items. Too many times do I see stubborn DPS say "NO I NEED MAI KOR ITEMZ I DUN WANNA BANSHEES INSTED OF MAI 2ND MALADY LOLOL." If you are getting focused, buy some defense items, seriously. 

AP Core Build:
Start out with a Doran's Shield and a HP pot.
First trip back, pick up situational boots (I go merc treads or sorc boots depending on their team) and if you have the money, start immediately rushing Rylai's Crystal Scepter. Whatever you have the gold for is fine, I usually get Blasting Wand first, followed by Giant's Belt, followed by an Amp Tome. 
After Rylai's, if you're doing well pick up a Mejai's Soulstealer. Nothing like snowballing Kat. 
If not, build a Zhonya's Ring. 
Then build a Deathfire Grasp.

Past this it's basically up to you, but since people see Kat and go OH GOD NEED MR, I tend to go with an Abyssal Scepter. If you seriously still have time after this, either pick up some defense items or cap yourself off with some ridiculous overkill item like a Lich Bane, or if you're feeling like some crazy vegan hybrid grab a Hextech Gunblade for the sick active.

AD Core Build:

(don't laugh, this is a serious build)
Start out with a shield and a pot, same as AP.

First trip back, get a Merc Treads or Ninja Tabi. you're going to need more defense in this build, sorc shoes are asking for you to be focused. if you're feeling good, and think you're going to roflstomp them, then by all means go for Sorc boots, though.
Next, farm 3 BF swords. 

No, I'm serious. Farm 3 BF swords. This gives you more AD for the money than anything else would, and since your early game is terrible since BF swords are so mofo expensive, you need to make up for it by quickly dishing out as much dps as possible mid-late game. If the game's not over by now, turn the first two of those BF's into Bloodthirsters, and the third into an Infinity Edge. Game's seriously not over? Jesus christ. Just get some health and go penta kill them, this game has gone on way too long.
---------------------------------------------------------------------------------------------------------------------------
There are a lot of other ways to build kat, but I find this the most efficient way to do it. AD is going to have some problems setting up their ultimate as compared to AP since it has less health and doesn't have the Rylai's slow, but it dishes out more damage in a team fight.

5. Gameplay and Strategy, during Early, Mid and Late Game

In this section I'll explain what you should be doing during early, mid and late game, including when you should have certain items built throughout the game.

Early Game

Do whatever you can to get your teammates to let you take mid-lane, unless there's a Heimerdinger or a Vladimir on your team. You are one of the best mid-laners in the game and there's very little that can easily best you in mid. Granted, you're a strong laner period and if you have to take a side it's not a big deal, but mid is where Katarina belongs 90% of the time. When the game starts, pick up a Shield and a health pot.

Pick up your first point in BB. Look at your mid-lane enemy. There are champions that Kat is good against and champions that Kat is nowhere near as good as. If you are laning against basically any ranged except Heimerdinger, Ezreal or Zilean, and possibly a good Vladimir, you're fine. You should be owning them once you hit level 6. Harass as much as possible with your Q as soon as you have a point in it, unless you're against something like Zilean, who can out-harass you 18 different ways. Shunpo and BB are both great for last hitting since the cost 0 mana, so be using them basically every time they're off CD. 
Your early game is one of your strongest points since you can 1v1 most champions at this point. I often have first blood as a mid-lane Kat. First trip back, grab boots 2, if you have the money buy a couple wards, and if you want them a few potions. If you still have leftover after that, congratulations, you're stupid awesome at farming, and pick up whatever you can to start your core build. By now, you should be at 80 or so minion kills and be level 10-11, which means that it's time for the

Mid-Game; Ganking and You

At this point, you are one of the best initiators for a mid-game gank because Shunpo ports you directly behind someone. Kill your mid-lane enemy and clear the creep wave. Have your teammates pull the enemies back a little bit, and go to whatever lane has a low-health or rather squishy character. Kill them. This will start the mid-game effectively and people will begin ganking each other. Set up wards while you're ganking to avoid being ganked yourself or getting counter-ganked. Once you're level 11 you can easily take out 2-3 people with your ultimate, especially if your targets are squishy. By this point you can own pretty hardcore. Help people push if you can, and also; I have to constantly reiterate this to people in normal queue. As a general tip, no matter what class you're playing, if an enemy champion is pushing a lane and no one is defending it.. go defend it. Letting someone push a tower with no resistance is just ridiculous. You might as well make your name "GiantNoob."

Early and mid-game are very important for Kat. If you're not getting kills and farming effectively then your damage and money gain late game will be gimped as hell and your DL won't be able to put out any damage whatsoever. Learn to play her well early and mid game and you will be set for..

The Late Game and Team Fighting

This stage is exactly what it sounds like. Team fights, team fights, team fights, baiting, team fights, team fights, team fights. Katarina can do one of two things in team fights. She can either clean up (i.e. going into a fight several seconds after it's started and hitting your ultimate after everyone's blown their CD's, allowing you to get off a lot of damage quickly without a lot of risk to yourself and most likely get at least a double kill) or she can set up her ultimate while the actual team fight is going on. She should be able to pop in and deal some massive damage before anyone is able to interrupt her or, if you don't immediately shunpo out, kill her. Positioning your ultimate is tricky, and I could tell you how I do it, but it's pointless to write out. You won't figure it out without trying it. 


6. Advanced: Juking and Katarina.

Juking is the act of confusing your enemies by doing things like jumping through a wall or jumping directly over them for getting away. There's nothing better than to have Garen chasing you with you at 500 health, hit him with Shunpo/exhaust and shunpo away again when he's sitting there confused, running in the wrong direction. This tactic is rarely seen at low Elo's. Why? Because it's difficult. To juke correctly you must have perfect timing and have wards set up strategically.

Here are some suggestions for learning how to juke: 

a. Always run with an exhaust. This will help you juke past someone more easily and possibly net you a kill while you're trying to run away. 
b. When mid-laning as Katarina, always set up wards in the side bushes and on the wall above them. It's fun to shunpo to a ward in the bush, have them follow you and immediately shunpo to the wall above. 
c. Try juking in a practice game with easy bots. This is especially effective on Twisted Treeline since the bots are more likely to run through the jungle after you.