First, let's take a look at the spells that are going to be your best friends while you work on leveling up:
Smite: Yes, I know. We've all heard the same LOLSMITE jokes. But when you start playing, it's going to be your only offensive spell for quite a while. (You'll first get Shadow Word: Pain at level 4, Mind Blast at level 10, Holy Fire at level 20, and Mind Flay, with talents, at level 20.) So at least until level 20, Smite is going to be your primary damage output. (Sure, you can alternate Smite with Mind Blast starting at level 10, but Mind Blast has a long cooldown.) Put it in a friendly place on your hotbar and get used to hitting that button often.
Power Word: Fortitude: This stamina buff is the first and most useful buff you'll get. More health can be the difference between life and death for you and the members of your party!
Shadow Word: Pain: When you get rank 1 at level 4, it hardly seems to do enough damage to make it worth casting (rank 1 does all of 30 damage over 18 seconds). However, it's a good idea of getting in the habit of slapping a SW:P on anything you're in combat with -- it does its damage over time, which means its sitting on your mob, dishing out hurt while you're doing something else. When you get Vampiric Embrace at later levels, it will also be healing you while you're doing something else. I don't think I need to explain how or why this is useful.
Power Word: Shield: PW:S is an instant-cast damage shield that can be cast on anyone in your party as often as every 15 seconds. While it's active, it also prevents spells from being interrupted by damage. When grouping, this spell is a quick way to save someone's life. And while soloing, the life you save may be your own. PW:S and heal yourself without interruption or PW:S and run away without getting dazed.
Renew: Renew is an instant-cast heal over time spell. It's handy because it's instant cast, so you can cast it on yourself or others while moving around. And since it works over time, you can cast it at the very first sign of damage and it will keep working while you (or the target you're healing!) continue to take damage.
Mind Blast: This is your secondary nuke. Why secondary, you ask, since it obviously does more damage than Smite? It's secondary because of its long cooldown -- 8 seconds. So when you first get it at level 10, you'll want to alternate Smites with Mind Blasts when your cooldown is up.
Psychic Scream: This instant-cast, AoE fear (you first get it at level 14) is a great way to escape from a bad situation. Surrounded by mobs beating on you? Hit Psychic Scream and start running. (While you're running, you can hit PW:S and Renew to make sure you're ready when they start chasing after you.) It's also great fun in PvP! Group of opposing-faction members causing you trouble? Well, if you're going to die anyway, why not disorganize them first? Run into the middle of the biggest group you can find and hit Psychic Scream. (Hey, even if you die immediately afterwards, it's always great fun.)
Mind Flay: Most noble of Priest damage talents, Mind Flay first becomes available at level 20, if you've spent all your talents in the Shadow tree, that is. Mind Flay is a channeled spell that does its damage over three seconds (one tick of damage a second, as well as slowing your target by 50%. Mind Flay does reasonable damage while being exceptionally mana-efficient, making it an important part of your arsenal. The spell's downsides? It can't crit and, because of the slowing effect, it only receives half of the normal bonus of spell damage gear.
Vampiric Embrace: VE is what makes Shadow Priests so special. Once you cast VE on a target, a percentage of the shadow damage you do comes back to your party as healing. So even when you're focused on doing DPS, you're also providing a bit of healing to everyone in your group. Excellent for grouping and soloing.
Now, as for talents, there are a few directions you can go, but regardless of what your spec is, your first five points need to go into Spirit Tap. Any of you who have played other classes are probably saying right now: but spirit is the most useless stat in the game! Why in the world would I want something that boosted my spirit after a kill?
When you've got the amount of spirit that Spirit Tap will give you, it's anything but useless. Spirit Tap makes grinding a breeze and means you'll rarely have to stop and drink. Just kill, run to your next target, attack, kill, repeat. (As soon as you can, I recommend locating a weapon with a lot of spirit on it to equip as soon as spirit tap becomes active. All of my priests pick up the Dancing Sliver as soon as they can manage the quest chain for just this purpose -- and slap a +20 spirit enchant on it. Even in Outland, enchanted, this makes a swell staff for mana regeneration with Spirit Tap.)
The next step, regardless of what build you'd like in the end, should be 2 points in Improved Shadow Word: Pain. This will increase the duration of your SW:P spell by 6 seconds -- thereby adding two extra ticks of damage. Even a Holy priest should be using SW:P to supplement their damage, so this is a great talent regardless of your build.
After that, however, you've got some options. You can continue up the Shadow tree, you can switch over to Holy if you want to do a Smite build, or you can briefly hop over to Discipline to pick up Wand Specialization (I know, wand damage is weak -- but for grinding/leveling, Wand Specialization is a worthwhile talent to improve your mana-free damage output. And with Spirit Tap, you usually want to wand for the last few seconds of any kill, so that when Spirit Tap hits you, you're already outside the five second rule.)
I tend to stick with Shadow for leveling up -- mainly because I want Mind Flay and Shadowform as quickly as possible. But many a Priest will tell you that the fastest leveling is to be had by picking up Wand Specialization and then respeccing at 40 for Shadowform.
After this decision, however, Holy and Shadow priests will be splitting ways. A Holy priest won't be grinding and soloing as fast, but will have some extra healing tools at their disposal which will help with grouping. In general, Holy leveling and Shadow leveling are two completely different styles. Because a Shadow Priest in Shadowform cannot cast any Holy spells (of course you can shift out of Shadowform to heal if need be, but this is usually a last resort, as it significantly decreases your damage output), they often won't be doing any healing (except with Vampiric Embrace) and find themselves acting like any caster -- attempting to kill their target before it is able to kill them. A Holy priest, however, has easy access a wide array of healing spells, and can use them to keep themselves alive in any situation.
However, before talking about the Holy tree, let's discuss the key talents in a Shadow leveling build. If you've picked up Spirit Tap and Improved SW:P, you need three points to get you to the next tier. I advise dropping these in Shadow Focus -- it's not a great talent, but for leveling it's certainly more useful than the alternative of Shadow Affinity, which is reduced threat. (More of a Shadow DPS grouping talent.)
Then you're up to tier 3 where you can snag Mind Flay -- which can immediately replace Smite as your standard nuke. At this point, however, there's not a clear way up the tree. There's a lot of personal preference involved in the rest of your talent selections. However, I'll point out some important ones:
Silence: This excellent utility ability will allow you to silence casters for 5 seconds -- though the pre-requisite of Improved Psychic Scream (neither a great talent nor a bad talent) may prevent some from picking it up.
Improved Mind Blast: A lot of people skip this talent, but it's always been a favorite of mind. If you max out Improved Mind Blast you'll be able to have a regular cast cycle of Mind Blast, Mind Flay, Mind Blast, Mind Flay, etc. I like having it (while leveling up I'll toss points in here as I need points to move further up the tree), but your mileage may vary.
Shadow Reach: Increases the range of your Shadow spells by 20%. More range means more time between your initial pull and the monster starting to smack you around, which results in improved survivability, which is a good thing.
Shadow Weaving: When you max out Shadow Weaving, every time you hit your target with a Shadow spell, it will leave a debuff on them that will increase Shadow damage taken by the target by 2%. It stacks up to 5 times for a maximum of a 10% damage increase of all Shadow spells hitting the target. Sure, this buffs your own spells, but often a mob is dead or nearly so by the time you've got it fully stacked, so I've always considered this more of a grouping talent -- and it's especially nice if you often group with a Warlock or another Shadow priest.
Vampiric Embrace: 15% of your Shadow damage now heals your party. With the improved talent (which I'm fond of), a total of 30% of your Shadow damage heals your party. Nice for soloing and grouping.
Darkness: Increases the damage of your Shadow spells by 10%. A no-brainer.
Shadowform: The end-all be-all for any Shadow Priest, Shadowform increases your Shadow damage done by 15% while decreasing your physical damage taken by 15%. Win.
By the time you've made it up to level 40 and gotten Shadowform, I'm going to presume you know enough about the class to make reasonable decisions about your future talent choices. Thus, I'm moving on to the Holy tree and our Smite build.
Your first points in Holy should go in Healing Focus. For two points, this talent gives your healing spells a 70% chance not to be interrupted by damage. It's great when you need to heal yourself while soloing, it's handy if you're trying to heal in PvP, and it lets you keep some control if you're in an instance and a pull has gone completely out of control. After this, there are only a handful of key DPS talents in the tree -- the rest of it is up to you.
Holy Specialization: For a full 5 talent points, gives you +5% to your Holy crit. Useful for both healing and Holy DPS -- though if you want to focus more on healing, it pairs nicely with Inspiration further down the tree.
Divine Fury: For 5 talent points, decreases the cast time of your Heal, Greater Heal, Smite, and Holy Fire spells by .5 seconds. As with Holy Specialization, this is a nice boost to both your healing ability and your Holy damage output.
Searing Light: Increases the damage of your Smite and Holy Fire spells by 10% for two talent points -- a cheap buff to your damage abilities.
Holy Reach: Increases the range of your Smite and Holy Fire spells by 20%, while also increasing the radius of your AoE heals (Prayer of Healing, Holy Nova, and Circle of Healing) by 20%. You'll notice the range improvements to Smite and Holy Fire far more often than you'll notice the radius improvements to your AoEs, though both are handy.
Spiritual Guidance: For five talent points, increases your spell damage and healing by 25% of your spirit. This is certainly a damage boost, but with limited spirit on most gear, it may not be much of one. I've always liked having it, but then again, my Holy spec priests tend to run spirit heavy, while you may favor the more practical approach of stacking intellect and stamina.
Surge of Light: The last DPS talent in the Holy tree gives you a 50% chance to be able to cast a mana-free Smite after you've scored a critical hit with Smite. It's mana-free damage for two talent points, which isn't bad.
And whether you spec Shadow, Holy, or some combination of your own, remember that for leveling up, you can't beat instance runs. They provide excellent experience as well as a chance at good gear. Healers are always needed, and, regardless of spec -- you can heal. And so long as you don't fall into awful instance groups, you could easily make most of your levels in instance groups.