Most people I see playing Nunu play him with a Rod of Ages and try to take advantage of his wonderful AP ratios. In this guide I'll illustrate an alternative way to play Nunu; you'll still get the most out of the base damage on your Ice Blast and Absolute Zero, and instead of using your (very impressive) scaling you'll take advantage of a Madred's Bloodrazor and Blood Boil to deal more consistent damage, with a more consistent slow from Frozen Mallet. And, being Nunu, your tankiness will not suffer in the slightest.

Patch 1.0.0.132
Stats:
Base attack speed increased to 0.625 from 0.613.
Attack speed per level increased to 2.25 from 1.08.

Because AS Nunu wasn't buff enough.

The differences between this build and a conventional Nunu build are minimal. Both deal lots of magic damage; both start tanky; both feature impressive slows. The main difference between the two is that while disruption (eg., Three Talon Strike) screws over AP Nunu, snares (eg., Dark Binding) can screw over AS Nunu. Both Nunus can turret dive, kite, tank, and really screw up someone's day.

We jungle, and so get Consume at levels 1 and 3. The extra level in Consume is recommended but not at all mandatory; post-jungle nerf, movement speed is an important part of jungling, so an extra point in Blood Boil at level 3 is perfectly viable. For the superior gank later, you might also consider a point in Ice Blast. The choice is up to you and your circmstance.
We aren't pre-buff Taric, so we get Absolute Zero at levels 6, 11 and 16.

Why do we take Ice Blast over Blood Boil if our intent is to deal damage through auto-attacks?
Well, at lower levels, Ice Blast provides more damage and a more significant movement speed debuff than Blood Boil is a movement speed buff, leading to stronger ganks. However, Blood Boil is a nice movement speed boost when trying to get between monster camps; pick whichever one you'd rather have (faster jungling? better ganks?) and your late-game damage and utility should be largely unaffected.
Note: Synergy with build should influence sequence. A build with early magic penetration (eg., Malady) would prefer Ice Blast more than build that relies on early on-hit effects (eg., Wit's End).

and Summoner's Resolve are pretty basic for junglers. With the new jungle nerfs, I find them to be indispensable if I want to stay at the level of my laning allies.
is what I generally go, because I enjoy being aggressive on Nunu (and taking easy early red buffs), but I concede that there are plenty of great options:
or are for chasing. I would pick Exhaust so I don't have to turret dive, but Ghost lasts longer.
keeps you useful if the opposing team picks, say, Morgana.
is an excellent pick for a Nunu who needs help landing his ult.
As for masteries, Defensive masteries help with jungling and allow me to focus on damage. If you have an idea for an alternative mastery, feel free to post it!

Greater Seal of Armor are used here for help in the jungle. This is pretty standard.
Greater Mark of Attack Speed and Greater Quintessence of Attack Speed are taken as this is an on-hit build and Madred's Razors don't proc themselves! You can take Greater Mark of Desolation, Greater Mark of Attack Damage, or Greater Mark of Magic Penetration, depending on the spec and personal preference. There really isn't a "right answer" as far as Marks and Quintessences go, though some options make more sense than others (you wouldn't want Greater Mark of Magic Penetration on a build with a Void Staff, for example).
Greater Glyph of Scaling Magic Resist is just for the tankiness. A popular alternative is the Greater Glyph of Cooldown Reduction for a faster Consume.
Any ideas for alternative runes are appreciated!

STARTING
is what you'll be running.
This is a pretty normal jungling build.

BOOTS
are my personal favorites. Harder Ice Blasts and great synergy with all our on-hit effects. Run these with an Malady; don't pick up a Void Staff.
are also an option. They are very cheap and an efficient way of adding AS to your Nunu.
will assist if dealing with a burst mage or chain (mitigate-able) CC.
allow for more aggressive gameplay and help with moving between jungle camps. The movement speed difference (normally rather negligible) is more pronounced by Blood Boil.

CORE

This is a great ganking set. Finish this up with a Madred's Bloodrazor, a Guinsoo's Rageblade, a Nashor's Tooth, and a Hextech Gunblade. Greater Mark of Magic Penetration or Greater Mark of Attack Speed are the suggested Marks for this build.
OR

This is probably the fastest clearing option. Finish this up with a Madred's Bloodrazor, a Void Staff, Youmuu's Ghostblade and a Hextech Gunblade. Greater Mark of Attack Speed or Greater Mark of Desolation are the suggested Marks for this build.
OR

If your team is losing and you realize you're going to take the brunt of damage in teamfights, choose this. Finish with a Frozen Mallet, Aegis of the Legion, Madred's Bloodrazor, a Sunfire Aegis and a Banshee's Veil. Greater Mark of Attack Damage or Greater Mark of Attack Speed are the suggested Marks for this build.
IMPORTANT NOTE: These builds are just ideas! Make up interesting combinations of your own (incorporate items not listed below) at your leisure! Feel free to post your builds in the comments!

LATE-GAME
is the annoying, percentage-based damage you've been waiting for. Nunu is one of the few characters for whom this item is actually worth every gold. Very important for this build as you head into the late game.
is an effective source of CDR. All of these stats are beneficial to Nunu, except maybe the crit; you have to remember to use the active in fights, though.
is my favorite chasing tool. Combine this with your Ice Blast and once you catch up to them they aren't getting away.
is an expensive but effective item. Some people replace Madred's Bloodrazor with this; I would replace Frozen Mallet or Hextech Gunblade, but that's personal preference. Ice Blast's low cooldown means that the passive effect can be up regularly, and Nunu's high base AD makes good use of it.
is useful for the attack speed buff and the bonus magic resistance. Only worth picking up if a chain-casting mage is giving you trouble. Generally, I replace Malady with this and buy a Void Staff later for the necessary magic penetration.
is going to be your source of magic penetration if you don't get any flat reduction or penetration in the rest of your build. That's really all there is to it.
has the largest amount of CDR of any item, plus constant attack speed and ability power (for Nunu's wonderful ratios), though it lacks the penetration, damage and Ghost active of the alternative. Replace Youmuu's Ghostblade with this if you are so inclined. There are definitely those who swear by it.
is an AWESOME item for the cost. For a more Ice Blast-heavy AS Nunu, the AP and AD and AS are just disgusting for just over 2000 gold. However, you need to be in a fight for a little while for it to become worth the cost. Definitely worth considering.
is a pretty solid item. You'll get the full bonus of the 35 damage every second, and the defensive stats will help you tank and turret dive.
is going to be your best counter to a bursty mage. If your team needs a tank because of a rampant AP Carry, THIS is what you NEED to pick up.
is an efficient source of tankiness. Pick this up if your team is losing teamfights and no one else has it.
is an interesting idea that was just brought to my attention. This item is fabulous on AS Nunu; highly recommended as a 6th item. (Read: you're fed or the game is taking a while.)

NOT RECOMMENDED
is not an item I recommend. It adds a bonus slow to your Ice Blast, which can be useful when facing someone really slippery like Kassadin. However, that ability is on a cooldown very significant in comparison to the length of Rylai's duration, so the slow isn't exactly consistent. Other than that, it's very important to be hitting the target repeatedly with your auto-attacks, so a Frozen Mallet should provide a more consistent and noticeable slow (as the two do not stack).
is a bad choice. Because the wait time for their effect is 5 seconds, it is not an effective means of moving between jungle camps more quickly and will be ineffective in teamfights.

I have tried Attack Speed Nunu in top lane, and it's perfectly functional (especially since the buff). In either position, Boots and Health Potions seem to be optimal. I am still working on this part of the guide; if you have an idea or an experience to share, I'll be happy to hear it.

I hope you enjoyed my build ideas and I look forward to answering your questions and comments!
Sincerely,
Pranzatelli

Special thanks to cybern8ic for his contributions to this page, and to Sk1llbug for the banner!