Ktarina is really fun to play. One of the most important things is to use all surounding units in your advantage. Examples:
Running to save yourself from an enemy, you see a minion/ally/ward/mushrooms/jack in a box or whatever, use your shunpo to get away from your enemy. chasing an enemy on low health in a lane, throw Bouncing Blade on the closest minion to the enemy champ to get a kill(occasionally).
Another main thing is to play rational. Dont play too agressive until you know what you are capable of with katarina.

The fact that she is an Ability Power champ and doesnt use mana or energy as a source makes her really easy to build. Just stick to flat AP , AP per level and magic penetration runes.

I play katarina full damage so i go allmost full offense and some utility. If you are new with katarina, you might want to take some mastery points in defence, but best to go full damage. About the movement speed in utility - believe me, you need it.

Items, as you know, depend basicaly on the enemy team.
Sell Doran's shield after lvl 10
If the enemy team has more AD champs, you might want to take Zhonya's Hourglass or Thornmail
If there are more AP take the Abyssal Scepter
As for the Hextech Gunblade, take it if you have free space in the item slots. About the mejai's soulstealer, it's not necesary to buy it, but if you get at least 6-8 stacks by level 10, you will deal a lot of damage.
Rylai's Crystal Scepter plays a keyrole in katarina s kills. It helps Death Lotus by slowing your targets and for assisting your team (yeah right :D)

My summoner spells are usually ignite and exhaust, but flash, heal, and ghost work as well
I know you all say "heal is a noob spell" but as a matter of fact, heal can save your butt if something goes wrong

Lets talk about Katarina s abilities. I love her passive because i can get a kill in front of turret with shunpo and then run away like a boss using shunpo on a targetthat is close enough to get away from the turret's attacks.
You Should Take Bouncing blades as first spell if you are up against a ranged champion.
Shunpo can be used to run down an enemy champion or to escape from one. It deals massive amounts of damage so when i am laning premade i take it as first.
Killer instincts is not much of a damage spell, but you should develop it at least once before level 6. If activated before you jump on an enemy using Shunpo and then Death Lotus, you are almost sure to get a kill unless your target flashes away or you get stunned/silenced/surpressed or simply tossed into the air. Dont be afraid to spam your abilities and dont save Death Lotus for later.

Killer Instincts and then bouncing blades ;)