Not Updated For Current Season
The masteries shown here are not yet updated for the current season, the guide author needs to set up the new masteries. As such, they will be different than the masteries you see in-game.
Malzahar has been my favorite champion since I was a little girl (for those of you who get that reference, congratulations!). The moment he came out, I bought him and learned how to play him. Using Phreak's guide as a baseline (which is what you should do. In most cases, Phreak is bad, don't listen to him), I figured out how I can play him and be effective at the same time
Marks: I choose Greater Mark of Magic Penetration as at low levels, doing more damage to your opponents decides who wins (which is why crit chance/damage Ashe builds do so much of your health low level. You can perhaps go with ability power ones, but I don't prefer them.
Seals: I choose Greater Seal of Evasion as what's better than having no damage dealt to you at all? Well, a lot of things actually, but in the case of a caster, not much.
Glyphs: Malzahar, like other squishy characters, is a caster. This means just about all of his damage comes from the fact that he smashes buttons. The sooner you can smash a spell again, the more damage you can do while minimizing the damage you take. That is why I go Greater Glyph of Cooldown Reduction. Obviously, you can choose to go the CDR/level ones, but I prefer the flat ones for low level spamming, as higher levels should give you more than enough CDR.
Quints: Malzahar is really, really mana heavy early game, especially being that I get Call of the Void first. That is why I get mana quints, though technically Greater Quintessence of Knowledge is better for you late game. This is entirely you're call, I tend to mix and match.
These items are ESSENTIAL for your Malzahar to not be dead most of the game. Depending on the match, you can either go Mercury's Treads or Sorcerer's Shoes. If the other team seems to be targeting you and you need to get out of their stuns / slows fast, get Merc Treads, otherwise get Sorcerer's Shoes to do more damage to everyone.
Hextec Revolver is a great item, and if you are just wanting to have a lifesteal equivelent, then by all means go for it or Will of the Ancients. Zhonya's Ring is good for those moments where you need a lot of ability power and to cheat death without needing a Guardian Angel. and Thornmail if there are a lot of troublesome Physical DPS-es. You may still die, but your team should be able to pick them off from the attack damage they have dealt to themselves (esentially).
Other Combinations for Summoner Spells
I personally go Clarity/ Ignite, gives you damage and mana in those "oh ****!" situations. Some other combinations I go in case I just have a feeling are
You can also substitute Ghost in for Flash, but that's up to your play style.
Clairvoyance and Teleport are also options, should they suit your playstyle
Spells to not get:
Revive: You plan on dying WAY more than you should. Don't plan on that.
Heal : Being squishy, the moments where you would be using Heal are moments that you are more than likely dead anyway. It's a waste.
Rally : ... as has been stated, if you're playing Malzahar with physical damage, uninstall LoL.
Exhaust : If YOU are the one on your team with an exhaust, things are probably going to end badly. Queue Dodge. Not even joking.
Grab Call of the Void and spam it 3 times while at your fountain. This will give you 1 harassing spell use, and another voidling summon. Most people just go up all the way, but I like to make the other person think they're in no danger before I rape them. Once you hit level 2, get Malefic Visions. You are still fairly mana heavy, so cast it only on the most dead minion near to you and if need be, attack it dead. It's about 2 or 3 bounces to get back the mana used for it, so be careful. Next get 1 point in Null Zone simply to scare people from your minions. Be careful and only use Clarity when you absolutely NEED the mana for it. Don't get down to low mana at level 3 and use it. that's what Malefic Visions is for.
At level 6, get your ultimate. No, I don't care if you've been doing good without it. get it. Nether Grasp is a spell not meant to be ignored on Malzahar. A level 6 Malzahar without it is a useless Malzahar. It deals heavy damage(1.5x your Ability Power) and surpresses them (meaning they cannot do anything).
If you've been doing very, very well, perhaps consider grabbing a Mejai's Soulstealer just to further your awesomeness (I never get it other than when joking around as I don't like the fact that I have to try and get all these kills and no deaths).
Do not engage team fights. Just don't. It's a bad idea for you and your teams ultimate victory. Let your main tank or off-tank go in first. Wait about a second, and Null Zone under as many of their team as you can. Malefic Visions the squishiest opponent, and Nether Grasp the largest threat. You should tell your teammates who this is so that they can help you to further kill them. If there is a Tryndamere on the opposing team, when you see his health get too low, silence. him. If he can't cast his ult, he can't live through the team fight to kill everyone.
A bit on some characters:
Ashe: Judge the level of the Ashe. If she crits you for half your health, note how far away she can hit you, and stay just behind your turret far enough that she will die, but close enough for you to get XP from the minions. Don't be afraid to Malefic Visions her to get her away.
Twitch/ Teemo : Personally, I love facing against these two characters, especially early game in mid. Here's what you do: Go out to your lane after spamming your Call of the Voids. Wait around a bit after the minions spawn to see if they will be in your lane. If they are, go back, and buy a Vision Ward and an Elixer of Brilliance. You will want to put it in the dead center/slightly closer to whichever side you find yourself more. If you are turret hugging, put it to your side, if you're pushing, closer to theirs. You should be keeping them as dead as long as possible. the only good opposing twitch/teemo is a dead one.
Malzahar : If you should face another Malzahar, you will be playing the "who can get to level 6 and ***** the other more" game. Keep an eye on how they move, and try to predict your Call of the Void casts to where they will go. Another way is to pray they won't notice Malefic Visions on the minions near them and get damaged by it.
Someone Tanky: Call for a ghank the moment your team can spare if they're good. If they aren't, keep them dead as long as possible.
Hope this helps. Feel free to vote/comment.