My in-game name is Beef Tacos and I am currently a Master Rank player (100+ LP) and I found success in Solo Q by playing Katarina almost every game. I've played with Scarra many times and he found my Katarina very good, so I decided to make a guide.

Katarina is extremely strong in Solo Q because she has high mobility, the best clean up potential, and has the ability to 100-0 someone with low cooldown abilities, and can make clutch plays against many enemies on your own.
Vods of me against Scarra (Can't attach video for some reason, sorry)
http://www.twitch.tv/scarra/b/579592830?t=2h22m40s
http://www.twitch.tv/scarra/b/579592830?t=2h25m30s

Against most match ups:
9 Magic Pen Marks
9 HP per Level Seals
9 Flat Magic Resist Gylphs
3 Movement speed Quints

Against AD (Zed,Talon,Yasuo,Jayce,Riven,etc)
9 Magic Pen Marks
9 Flat Armor Seals
9 AP per Level Gylphs
3 Movement speed Quints

Katarina needs survivability as you will be soaking quite a bit of damage, and you need the movement speed because Katarina really needs the speed to get onto a good target and proceed to get resets. Movement speed quints are far superior against AP quints overall, as this will help you roam and snowball.

This setup may look a little weird, but it is actually the best setup because Katarina's weakness is her laning problem, and taking the AP mastery isn't as helpful as the AD mastery because Kat's basic skills don't benefit that much from AP, while AD will help you last hit and potentially trade with auto-attacks against certain match-ups. The rest are pretty standard mastery investments.

You want to get a deathfire grasp as soon as possible because that will enable you to start snowballing and get easy resets. This item can lead you to getting triple kills with ease. I would only rush Zhonyas as a second option if I am against Zed or if I'm just straight up losing really hard against a burst champion. For your second item, get either deathfire grasp or zhonyas depending on which item you didn't buy first. The reason why deathcap isn't as good for a 2nd item is because in team fights you will need the zhonyas active at one point and it will help you make cluth plays where you need your teammate to finish that low hp guy off so you can get resets, and zhonyas stalls for that short time so you can get out safely. I would only buy deathcap before zhonyas if the game is a stomp.

For more damage

If they stack MR

Very strong item in team-fights because it is basically a Quicksilver Sash and a Zhonya's Hourglass into one item. This item will basically remove cc from you because after you die there is a revival period. You want to dish out as much damage as possible and die with this item, so your team finishes the enemies and you have resets to go back in or get out.

Honestly do not like this item. Even if you have a double AP comp against a double AP comp, this item doesn't enable you to snowball in Solo Q. This can be a good choice for beginner Katarina players.

Many players like to rush this, but I don't like it because it delays your core items and early game fiendish codex+ hp pots can do the same trick as a haunting guise. Sure, it give's magic pen, but honestly it's not a good power spike. The Kat players in Korean Solo Q like to rush haunting guise into abyssal scepter and never buy deathfire grasp, but the meta there is different from NA.

Maxing Q first gives you the most burst possible and helps you clear waves potentially faster than maxing W, but I actually prefer to max W against melees such as Zed or Yasuo because you can harass them and easily run out with the burst of speed. Maxing W also helps you farm wraiths/wolves drastically faster. Shunpo does the least base damage and it's just a gap closer so max it last.
= freelo. You get a powerspike each time you level your ultimate.

+I always take ignite flash. Ignite helps you have more killing power, and sometimes it gets you a reset that leads to multi kills. Ignite is basically a summoner spell that potentially deals 1000 because of this. I also take flash because many players can't react fast enough when a Kat flash shunpo's and oneshots them. I've seen some people take teleport and use it to get kills across the map to snowball, but I don't like it because your killing power in skirmishes become lower.

Pros:
High Burst
Best clean up potential in the game
High mobility
No skill shots
Easy to dodge enemy skill shots with shunpo
Can destroy people with low cooldowns
Easy to play

Cons:
Weak laning phase
Can lose alot of pressure if you don't stay atleast even
CC can shut her down in team fights. (Especially fiddle's fear, and rammus's taunt)
You need decent mechanics to be able to play her effectively
People may bash you for playing a "no-skill" champion

+ You can use a yellow trinket or wards to jump to them with shunpo, which is basically a flash for 75g or for free. Try to conserve flash because it wins you team fights.

You can use death lotus even if you don't see the enemy. So if your death lotus icon glows up when you are near a brush, you might be facechecking into danger so either ward that brush and go ham or just ward jump out immediately. You can also use this tactic to hit a stealthed twitch with your ultimate, or use it to locate and damage an Akali that is in her shroud.

If you are against a laner that can harass very well, you may need to use your Q just to last hit. It can be annoying since your Q un-intentionally shoves the lane towards the enemy. Try to farm up and if you max Q first don't bother doing wraiths unless if you know the enemy mid laner recalled because it can waste alot of time and you will take considerable damage. Honestly in Solo Q your farm shouldn't be that important on Kat because you just want to kill people and take control over objectives like Dragon and Baron since you have strong aoe dmg.

Katarina can get shut down in team fights due to her being very vulnerable to hard cc. Try to wait until someone is low so you can get a fast reset, or just wait til the enemy uses their hard cc on someone else. You can also surprise them by flashing onto their carries while the enemy CC champions are far away from the carries. You can also tell your support to buy aso you can go ham. Don't feel bad if you are waiting around the fight waiting for someone to get low. The key to Katarina is patience, you really need to successfully get resets to win the team fight.

This guide is not completely done yet, so more updates will come in the future. For now I hope you learned a thing or two about Katarina and good luck climbing the ladder. pictures soon to come lol