To start, there is only one way to do Maokai justice, and I'm going to explain how. Most of this has been found out through trial and error, and getting sick of the usual Maokai failures. Anyway, to business;
Maokai is not a tank, if you think he is, stay away from him. Maokai is rather unique in LoL, he's not really all that AP, because items take too long to become effective. He's not a full tank, because that'd remove a large portion of his effectiveness. He's not AD (lol really).
The current problem for Maokai is that most people don't have a brain. They build the basic AP or just slap on some random Tank items and fail.
To do Maokai justice, one must look at what Maokai actually NEEDS and at what he can really DO. The things Moakai needs are;

• Mana
• Health
• Little more health
• Some damage resistance
• Quick and early damage
• Mana
• Mana
• Mana
• And something to make his ult even nicer than it already is.

What Maokai can DO is;

• Save/support his team by using his ult (20% damage reduction and bonus from Aegis is just an insane improvement for most teams)
• Initiating fights
• Last long enough to survive and do damage while doing that
• Do serious damage with his skills combined (his burst is SCARY! - at least with this build)
• Early game owning

Now, to how we get all these things;

Runes, basic magic runes. Many use em. You have the MP for more damage, the Mana because even with Chalice you can sometimes use the extra mana, the cooldown, because maokai is a bit difficult late-game, and this solves that problem completely.
HP runes because you want to dominate your lane from the beginning of the game, this helps with that. Together with your masteries, you can be a solid presence, no matter if you're solo vs 2 or just in a lane. Nothing can kill you unless you REALLY want to get suicidal, and lets say for the sake if this guide, you aren't, yet.

You start the game with;
And some potions if you so desire. You could also start with Doran's Ring, but hey, whatever you like in this scenario. I like to get straight onto the killing, but if you're 2v1 in a solo lane, you might want to consider Doran's for some more health!

Chalice of Harmony. This is what you get BEFORE your boots! Best is to go back and finish this and buy basic boots in one go. Depends on how your lane goes. Many say this item sucks, well, guess who's wrong? This gives you early magic resist and mana regen. Actually exactly what Maokai needs early game!
For boots, we take what fits Maokai best. You got basic magic resist with chalice and tenacity isn't really what you're worried about with Maokai, you take the next best thing;
Kind of figures right?
Now on to the crazy stuff! Again, an item people don't use because they don't appreciate it. How stupid. Your third (4th if Dorans') is this;
OMG WHAT? Yes. This gives you Magic Penetration! Throw a sapling and see for yourself, this makes you a killing machine and gives you health and some AP. Exactly what the doctor ordered! Yes there are items with more health, sure, but they're also crazy expensive. This puts you ahead of everyone else in the game already because these few cheap items make you SERIOUSLY dangerous. At the moment when you get this, others will be saving for a rod of ages still and only have a few more HP. You do tons of damage!
Another thing, this gives you 49MP total (incl. runes), this will HURT everyone, all your spells will now hit for 100% damage on almost everyone. That's sometimes even more than 100+AP can give you. Try and see for yourself.
Best thing about it; this gives you a SERIOUS damage boost to your ult. Think 700+ damage straight. Call it True damage if you like now, because for most, it'll definately feel like it.
Now, to the 4th item;
After going for damage previously, this might surprise you. This is cheap, puts you in top shape for tanking however, especially because at this point, most tanks have only finished one item. Also supports your team and works well with your ult! Doesn't makes you the top tank, but it makes the entire team a lot more tanky. Gives you and above all, your team a serious edge. If you have enough brains to place ult.
From here, do as you please. I've added Abyssal Scepter, gives you great magic resist and makes you a great magic tank. Also added Sunfire, the magic damage from this get magic penetration too, so actually HURT LIKE HELL to anyone standing close.
The magic pen from abyssal can go below zero too, not sure how that works, but bonus damage could be involved.
Sometimes if a game goes really well and there's another tank, Rabadons is hilarious. AD items are funny too, Nashor's Tooth will leave an impression.

Not much to say about this actually. Just improve your sapling first. Then Twisted Advance, because with this build, you WILL initiate all the teamfights. - which is how you position your ultimate correctly by the way.
Don't forget to get one lvl of arcane smash at lvl4, this will save your butt a few times, and it slows. You will like both. Damage is actually impressive, but for teamplay you want the twisted advance first.

Initiate.
That's all there is to it. Harass lane with saplings, because with chalice you have infinite mana, spam them saplings 24/7! Save one for a fight though, they hurt like hell if you twisted advance/root them first.
Start teamfights, watch the map. With Maokai like this, it is not unusual that you'll gank mid in case of trouble. (really, sounds strange right? You will!) Or you gank the opposite lane, anything that suites you. You don't need the kill because your items are not so expensive.
In teamfights, Maokai is meant to be FAST, you initiate from lvl2 and if you have a lane partner with atleast half a brain, he'll know that its time to do some damage too. I've not found it uncommon to have double kills at lvl2 or 3. All you need to remember is;
W E R Q. That's all that there's to it. The last Q is for the slow mainly. And disrupts your opponent a little too. At lvl2 it'd obviously be E R.

You don't need much, but from lvl5 or so, your sapling almost kills rear minions in one blow. Finish with Q. From lvl6/7 you dont need Q nomore! Your AD is nice enough to take out a tower, or 9.