Lane shove, early skirmishing, and [R] spam.
Empowered abilities and resource manipulation
Hitting a champion with spells hurls a comet that deals adaptive damage at them. Landing more spells reduces Arcane Comet's cooldown.
Gain cooldown reduction and max cooldown reduction on your ultimate. This is increased further each time you use your ultimate, up to a maximum.
Gain 3% extra MS. Gain extra AP or AD, based on your bonus MS, Adaptive.
Your first ability hit every 20s burns champions.
+20 Ability Power or +12 Attack Damage, Adaptive
+5% Max CDR
+5% Summoner Spell CDR
+5% Item CDR
You get free boots at 10 min. but you cannot buy boots before then. These boots give additional MS. For each takedown you acquire the boots 30s sooner.
Malzahar's kit allows him to repeatedly proc Comet on cooldown and reduce it's cooldown effectively with [E] and [W]. Once you've purchased Rylai's your comet hit-rate will skyrocket.
The more your [R] up the more kills you can secure for your team. Paired with Transcendence and Cosmic Insight you'll have your Ultimate up for any fight or skirmish.
If you'd rather spam abilities for harass, take Manaflow Band.
Celerity is a great rune on Malzahar largely thanks to the passive Movement Speed. The extra bit of speed allow you to get into range of that clutch [R] that you might not otherwise be able to get.
The option here is really a personal preference. Scorch is great for lane harass and early fights while Gathering Storm is great for scaling and pairs well with Magic Penetration.
If it looks like your game might be stalled out by wave clearer (Anivia etc.), you can take Gathering Storm for scaling.
Malzahar loves CDR for both his [R] and harassing/shoving in lane with [E]. Assuming you've completed Morello's, you'll already be at 35% CDR and incredibly strong at 10min.
Magical Footwear is a great rune choice for simply saving money so you can hit your damage power-spikes that much sooner.
If you prefer to rush Boots to catch your targets in [R], take Perfect Timing for a cheaper Zhonya's.