Katarina is generally regarded as a weak champion, and easily countered in team fights. However, I mained her to the top 100 solo queue and feel she is a decent champion with few counters when played correctly.

I attempted to simplify, but the optimal build for Katarina changes from game to game. I always run at least two different rune and mastery loadouts to use depending on the team makeups, with item builds varying immensely.

Note: this guide is a partially updated repost of my older 2k guide.
I took a 4 month break from LoL and now my internet is too laggy to play ranked, so I can't properly update the guide.

Hard laning counters (I cannot lane against them as Kat):
Kassadin, LeBlanc, Tristana, Xin Zhao.

Soft laning counters (they always out CS me):
Sion, Malphite, Blitzcrank, Fiddlesticks, Annie, Zilean.

Champions to be scared of in team fights:
Kassadin, Blitzcrank, Alistar.

Flash can be used either to escape or to kill, and the range on Flash -> E -> Q is amazing.
Ignite is powerful in the lane, and helps to proc Kat's passive early in a team fight.
Exhaust and Cleanse work okay too, but they won't help with laning as much as Ignite.

9 / 0 /21 is what I currently use.
The experience gain makes it so I can push a lane a bit right before leveling, and be one level up on my opponent for one creep wave.
Also, the CDR on summoner spells makes them more reliable for escaping ganks or getting kills.

9 /21 / 0 works as well, although I find it fades off late game.
The primary reason so many people use defensive masteries is for the extra survivability during the laning phase.

Marks - 9 x Greater Mark of Magic Penetration
Seals - 9 x Greater Seal of Armor (optionally Greater Seal of Vitality)
Glyphs - 9 x Greater Glyph of Cooldown Reduction
Note: use Greater Glyph of Scaling Cooldown Reduction if you're running defence masteries.
Or for laning against AP champions: Greater Glyph of Magic Resist
Quints - 3 x Greater Quintessence of Ability Power
Optionally: Greater Quintessence of Health (especially in 3v3) or Greater Quintessence of Movement Speed

Q Bouncing Blade
Main farming/harassing tool. I max it first.
At high ranks, there's no need to target the opposing champion while laning. I just cs with Q and it will usually hit the champion from a safe range.

W Preparation
I put one point in it at 3 or 4, depending on whether or not i want the healing debuff. In team fights I often use it with shunpo first, and early ignite if I need a healing debuff.

E Shunpo
Powerful survival and chasing ability in team fights. Can use on wards or combine with flash for some pretty epic escapes/chases.

R Death Lotus
Main damage ability in most team fights, but easily countered. Don't use it too early.
It's easier to get positioning for Death Lotus with more survivability gear, at the tradeoff of reduced damage. Team compositions also affect it.

Here are some tips:
- Wait until the nearest CCer is CCd
- Death Lotus can be used through walls
- If the enemy is focusing you, use E defensively and save ult
- Ult when a teammate is low hp and being focused, as cc spells typically deal damage (i.e. Sion's Cryptic Gaze or Singe's Fling)
- Most CCers use their abilities early in a fight as part of their spell combos, so typically you only have to watch out for one or two people once the fight is initiated
- Death Lotus is a ranged spell, so there's no reason to be standing next to an Udyr or a Blitzcrank while using it

Against a physical damage champion (i.e. Renekton, Garen, Pantheon, Ezreal, etc.) start with Cloth Armor and 5 x Health Potion.

Against a level 6+ Fiddlesticks, don't be predictable about when you move near creeps or he'll Crowstorm from the bushes.

Against a level 6+ Morgana, leave a ward in the middle of the lane so you can Shunpo out of her ultimate when there aren't creeps around (the same tactic works against anyone with a strong initiation, like Garen or Blitzcrank.)

Against a healing champion like Nidalee or Vladimir, keep a healing debuff active as much as possible. Break Garen's passive with Q.

Use Death Lotus to harass; it has a short CD.

Most champions can kill Kat 1v1 if they haven't first been harassed low with Bouncing Blade.

If an opponent gets low enough to recall, wait for cooldowns before using Flash --> Shunpo to tower dive.

When taking top solo from the northeast spawn, place your river ward next to the ridge, allowing you to Shunpo to it after turret diving to avoid a gank.

I normally start with Boots + 3 x Health Potions.

If you aren't going to read the approaching text, just build:


If my lane is evenly matched:
Giant's Belt --> Rylai's Crystal Scepter.
Or: Ionian Boots of Lucidity --> any part of Rylai's Crystal Scepter.
Sorcerer's Shoes are good if my laning opponent has low mr and I don't need survivability, but if it's possible to save enough gold, a Giant's Belt is better.
Once I feel I'm farmed enough to stay alive in a team fight, I'll start work on a Hextech Gunblade, unless my team has a lot of CC and a healer, in which case Rabadon's Deathcap is better.
The game should be decided before I can get another item.

If I'm crushing my lane:
I typically go Bilgewater Cutlass --> Hextech Gunblade.
For team fights I sometimes rush Ionian Boots of Lucidity.
Depending on the amount of gold I have when I buy, whether or not my opponent is stacking MR, and how much I need survivability, I might first buy Sorcerer's Shoes or a Haunting Guise.
If my opponent uses one type of damage, I might get a Chain Vest or a Negatron Cloak, respectively (especially if expected ganks use the same type of damage.)
I'll eventually want to build a Rylai's Crystal Scepter and a Rabadon's Deathcap.

If I'm getting crushed, then my buys depend on my team comp:
With a high CC team, I stack damage and only fight when my team is laying down CC: Ionian Boots of Lucidity (for the Shunpo CDR to stay alive) and Rabadon's Deathcap
With a low cc team, I stack tank gear to stay alive in fights until I'm strong enough to build AP and acquire a slow:
Giant's Belt, Chain Vest and/or Negatron Cloak, and then I finish a Rylai's Crystal Scepter as soon as possible.

Tip: if you're losing, only itemize for team fights, because the easiest way to get back in the game is to group and gank or perfectly initiate a 5v5; therefore, Sorcerer's Shoes and Hextech Gunblade are poor buys.

Hextech Gunblade is an amazing item for its powerful nuke + slow + ap/ad, and snowballs really well because I can farm a creep wave to regain all of my hp after a team fight; however, it's a bad buy when I need survivability.

Building a Gunblade:
If I'm winning the lane (i.e. Gunblade is my first item) and don't have enough gold to straight buy a Bilgewater Cutlass, then Pickaxe + Health Potions is better than a Hextech Revolver. The cooldown on Shunpo is fairly long during the early game, and extra attack damage not only buffs Bouncing Blade for lane control, but allows for easier last hitting when pushed into my tower, or better turret pushing when my opponent leaves the lane.
If I'm a high enough level to have Shunpo maxed, and I already have a Rylai's Crystal Scepter for a slow, then Hextech Revolver is better than a Pickaxe.

Rabadon's Deathcap is normally a late game item, partly because its passive is better with additional items, but primarily because Kat needs survivability + damage + a slow, and Rabadon's is a lot of gold for just one of those features; if my team composition allows me stack AP, then it becomes a stronger early game buy.

Sunfire Aegis is great against any team with a lot of physical damage (i.e. Shaco or Master Yi Jungling + AD Carry or physical bruiser like Renekton solo); its damage is magical, and I usually have some magic penetration.
Update: this guide was written when the metagame was dominated by bruisers, against whom Sunfire Aegis shines; now that healing and burst casters are more prevelant, it may not be a strong item on Kat.

Abyssal Mask is amazing because it provides both MR and AP; however, if the other team stacks MR, then the passive on it is pretty useless. It's basically the MR equivilent of a Sunfire Aegis.

Void Staff is essential if the other team is stacking MR, but since it's rare for much of a team to buy MR, it's usually a 5th or 6th buy.

Haunting Guise is a great item if I'm super fed early on. For roughly the same cost as a Mejai's Soulstealer, I get enough magic pen to replace Sorcerer's Shoes, and some survivability to support my Hextech Gunblade. Often, it's a better judgement call to put the gold towards a faster Rylai's Crystal Scepter.

Mejai's Soulstealer is a terrible buy. If I'm able to get Mejai's stacked, then I could have won the game more easily with a Haunting Guise. The only time a Mejai's will actually pay off is while carrying newbies in a normal game.

Quicksilver Sash is great against Malzahar, Warwick, Alistar, and Blitzcrank. The idea is to break a stunlock so I don't die in a Malz ult :(.

Banshee's Veil is a must buy against a few combo teams, similar to a QSS . I always get one when fighting a Veigar.

Boots:
Sorcerer's Shoes are sometimes the best choice because they will bring a squishy champion close to zero MR. However, if the other team is stacking MR, then Sorc boots don't add much damage.
Golem buff + Sorcerer's Shoes is incredibly powerful early game.

Mercury's Treads are necessary versus any team with a lot of CC (assuming no Cleanse or QSS .)
Update: Moonflair Spellblade has now been released, and may be a viable alternative to Mercury's Treads.

Ionian Boots of Lucidity are usually the best boots for Katarina (add an Elixir of Brilliance and it's 40% CDR.)

An Elixir of Brilliance is good for team fighting because it's cheap CDR with some AP to boot.

Firstly, a shorter CD on Shunpo will keep me alive in a team fight long enough for someone to die to proc my passive. Often I have to save Shunpo to use defensively (i.e. to dodge Kogmaw's ultimate .)
Secondly - and this is huge - CDR allows me to ult before someone dies, and then ult again after only two enemy champions have died instead of three.

The Math:
Rank 3 Death Lotus has a 50 second cooldown that starts upon casting the 3 second channel, leaving 47 seconds until it can be used again. Two procs of voracity bring that to 17 seconds. 17 divided by 50 = 34% CDR needed to negate the cooldown if two enemies die during the channel. Flat CDR Runes + 9/0/21 Masteries + blue elixir = 25% CDR, which means that if two enemies die, only 4.5 seconds remain after channeling before I can ult again (and that's only 250 gold spent on CDR).
Rank 2 Death Lotus has a 55 second cooldown, so either Ionian Boots of Lucidity or Golem Buff is needed to ult twice in one fight.

14 Aug 11 - added a sample item build to the summary to make the guide look more complete