Update! I've added a fifth post, which discusses the new skills added in the Realm of the Diggle Gods expansion, as well as describing some new builds they make possible.
Option 1 - Obvious Power Builds
The Heavy Thumper - Maces, Shield Bearer, Berserker Rage, Master of Arms, Flesh Shaping, Assassin, Smithing.
This is the classic heavy-hitter build. Take Smithing level 2 as your first skill - it gives +1 melee damage and +1 traps, so you can earn lots of early experience by disarming. Take Suit Up, Walk it Off, and Dwarven Handshake next. Probably in that order, but DH can be taken sooner if you need more damage quickly. The only other crucial skills are to get Knit Tissue and Smithing level 5. Smithing is better than more Mace skills, because it gives you just as much damage increase (thanks to the Burliness bonus) and ALSO lets you craft flails asap - which will really help your damage output. Keep Meatshield up mostly for the awesome double-speed regeneration, but be wary of losing it during combat!
Getting 2 levels in Shield Bearer will give you Defensive Bash- which is a great damage/knockback move. 2 levels in Berserker Rage will give you big damage / armor bonuses when fighting groups. Pick one of those to grab next, and grab the others eventually. That takes you through level 15. Assassin has lots of stun/damage/accuracy/critical bonuses, but you need to invest 3 points to start improving them, so it's something to save for later.
You don't want Flesh shaping past level 3, you don't really care about Master of Arms or Shield Bearer beyond level 3, and while you desperately want Maces level 2, anything beyond that is of pretty marginal utility to you. All of those are gravy skills you take because you're kicking so much ass. (Update! As of v1.0.10 Maces level 6 is godly. GET IT.)
The Magical Overlord - Staves, Golemancy, Mathemagic, Promethian Magic, Magical Training, Ley Walker, Alchemy.
This is the best way to get your magic fix on in relative safety. Use Blade Golem and Firebreathing, along with limited melee attacks, and hopefully a well-placed arrow trap to defeat early enemies. Your first skill is Golemancy's lovely Animate Moustache, and you're untouchable for a few levels at least. It's possible to skip Animate Moustache if you're clever, but it's not my suggestion for most players. Next get Ley Walker #2 - for mana regen on demand.
Your next skills are, in any order, Alchemy #2 and #3, Magic Training #2, Rune of Exploding, Wyrmling, Beklam's Diminishing Calculus, and Golden Ratio. Alchemy and Magic Training will push your power and cut your spell costs - which is good. The other spells are just useful toys to play with. Golden Ratio is a bit expensive early on, but it's fantastic. Eventually you can take Obvious Fireball and ZenziZenzizenzic, and start to really plow your way through things.
After that point you have a few more options for your end-game spells. Recursive Curse is a proven Dredmor-killer, and Thaumite Swarm (#4 in Golemancy) is a great way to clear out groups. You do NOT want to put more points into Staves, you do NOT want to bother with the Mortal Machine, and you do NOT want to both with Infernal Torus. Finish up Alchemy, Magic Training, and Ley Walker instead.
The Untouchable Ghost - Swords, Dual Wielding, Astrology, Burglary, Fungal Arts, Archeology, Tinkering
This playstyle requires a bit of finesse and inventory management, but it can absolutely handle anything in the game. Get used to employing Lucky Pick, Mushrooms, and Radiant Aura at every opportunity. Slime-herder is your first skill. Lucky Pick, Lockup and Ninja Vanish are next. After that you either take a level of Swords, for a bit of damage, or you start taking Traps. Move in Mysterious Ways is amazing - get it eventually.
You don't need any skills in Dual Wielding, Astrology, Swords, or Fungal Arts past level 2. This means you are essentially "done" with skills by the time you reach character level 12. You should have hundreds of mushrooms to buff yourself + heal, lots of traps to lay down, lots of bolts to fire (and an awesome crafted crossbow), an infinite number of picks, and huge melee damage + counter hits. The only thing you DON'T have is decent defenses, so pick your battles well and stay at range when it is prudent to do so.
Update! Mushroom creation rate now starts a bit lower - and gets much better as you increase your Fungal Arts skill level. That makes points past level 2 not a terrible idea, though it's not really something you need to rush.
Option 2 - Builds that make odd skills shine.
Sometimes you don't want a cookie-cutter power build - sometimes you want to challenge yourself with something a bit odd.
The Fighter-Mage - Staves, Dual-Wielding, Berserker Rage, Vampirism, Viking Wizardry, Blood Mage, Alchemy
The goal here is to push your combat abilities without hurting your Magic Power. That means very little Heavy Armor, which makes you prone to taking a lot of damage. On the other hand, awesome damage spells backed up with dual-wielded staves is pretty sweet. Take Drinker of the Dead first, to keep your health up. Now split your next few skill points between Staves and Viking Wizardry - you won't have enough mana to use the spells a whole lot - but getting some early practice in is a very good thing.
Once you reach about level 6, it's time to focus on alchemy. You need health potions to get yourself out of jams- along with potions of replenishment, invisibility, and purity. You also want to craft yourself a couple of great staves to wield. Alchemy levels also increase your Mana and Magic Power significantly. After Alchemy, you should finish off the Staves skill tree. Eventually you'll find yourself wanting to cast spells more and more - that's when you pick up a level or two of Blood Mage, to keep yourself topped-off. Another fun thing about this build is that the third Vampirism skill - Sparkly - is really worth getting.
This build has very few skills - most of them top-off after just 2 points. So this is one of the few builds in which you will very likely take every skill if you survive long enough. Dual Wielding is absolutely your least important place to put skill points, if you make it that far.
The Necromancer - Staves, Shield Bearer, Artful Dodger, Flesh Shaping, Necronomiconomics, Astrology, Alchemy (option: switch Artful Dodger for Archeology)
This is all about making Necro work for you. For those who haven't tried - Necronomiconomics is a very powerful skill tree - which deals heavy damage to you. This makes it a poor measure of last resort - and a poor skill set to use frequently. In order to use it at all, you need to collect and manage gear with Necromantic Damage resist. Astrology can do some of that with its buff spells, but you need to be on the lookout for rings, artifacts, and the like.
This build begins by building up Alchemy and Staves. Keep Radiant Aura up, and you can cast a few Deathly Hex bolts without too much trouble. Do NOT use Meatshield in the early game - you can't afford the upkeep costs. It's a good fallback to save you and regen up health, but not something you want to use often. Once you have at least level 3 in Staves and Alchemy, it's time to start grabbing levels of Necro. Your goal is Pact of Fleeting Life - which gives you huge lifesteal abilities - you can wade through monster zoos without trouble in many cases. The last two Necro spells are area-effect blasts which are powerful, but dangerous to cast without lots of distance between you and your targets.
Speaking of distance, get Knightly Leap by level 9 or so. That and invisibility potions are your two best ways to escape. Ideally you will have no need to escape... but a bit of insurance doesn't hurt.
When I play this build I don't take any Flesh Shaping skills, but getting Zombyfycation and Corpse Explosion would be thematic. I also don't generally take additional Astrology skills, but Celestial Aegis is a great way to mitigate Necro damage. Shield Bearer is a fine skill all the way through - you won't ever make a mistake by taking its skills on occasion. Maximum-level Staves and Shield Bearer, with duck & cover and tortoise maneuver active, will absolutely keep you safe while you wade through enemies with your death-touch.
The Peltast - Maces, Thrown Weaponry, Artful Dodger, Perception, Smithing, Tinkering (7th skill is Piracy if you have RotDG, otherwise Bezerker Rage)
Do you like to carry a lot of crap around? And hurt people with it? Then you'll love this build. The goal here is to make maximum use of Thrown Weaponry. Thrown Weaponry benefits from melee bonuses, so we mix in Warrior skills and Smithing to boost our damage. Smithing level 3 allows us to make Throwing Knives, Darts, Javelins, and Throwing Axes. Levels 4 and 5 offer only minor improvements, so they can be saved for later in the game, when you need heavy armor. You don't need Magic Power at all, so heavy armor is your best defense. We use Maces because mace level 2 gives us the awesome Dwarven Handshake - which can knock enemies away and give us room to throw things.
Smithing level 2 is your first skill - for the +1 traps! Then Maces level 2. After that you want to increase Thrown Weapons to 3, get Smithing 3, max thrown weapons, and start getting levels of Tinkering. Knightly Leap is a good option as well. Tinkering only needs 3 ingredients - iron ingots, black powder, rust, and aluminum. (for thermite bombs!) Smithing thrown weapons only needs iron ingots, brass (copper + tin) ingots, hefty sticks. Buy any rough iron axes, to upgrade to throwing axes, but don't smith any yourself. (10 daggers is better!) Tinkering increases the number of bombs you can make with your gunpowder, so hold off on crafting those weapons if you can.
If you need more damage, increase Bezerker Rage. It also gives Warrior levels - which will increase you melee damage bonus (and thrown damage bonus!) Perception is strintly thematic, though it offers solid bonuses and the amazing Eye Lasers at high levels. If you have Piracy, you can create cannotballs with the last skill - which are totally decent thrown weapons.
The Honorable Monk - Unarmed Combat, Shield Bearer, Artful Dodger, Bezerker Rage, Psionics, Burglary, Assassination
Do you like to run lean and fast? Too much stuff weighing you down? Then you'll love this fleet-footed build. Start with Throwing Buffalo Technique right away, then get Shove, Healing Crystals, and Knightly Leap. After that there really are no bad options - every skill in this build is an effective part of your character. Defensive Bash gives you additional knockback attacks, and with two shields and a few levels of Shield Bearer you should be blocking a LOT more than you are probably used to. Knightly Leap is an interesting skill here - I tend to use it to leap INTO combat more than out - because up close I can lay down the smack.
Assassination and Burglary are the effective utility skills they always are - and Burglary level 3 gives +1 traps, which you should realize by now I consider a tremendous early-game advantage. You absolutely NEED to maximize Unarmed Combat by the time you reach the fourth floor of the dungeon - because your melee power will start to come up short a whole lot. Unarmed Combat starts weak, gets strong in the mid-game, and then becomes pretty weak again by the last few floors. You need back-up damage, which is where Unconditional Love and Assassination come in. Lockdown and Sleep (along with your 4(!) knockback skills) should help you to pick your battles carefully.