I'll ring in on my opinions, hopefully some others will too.

Shaman pvp: http://www.wowhead.com/?talent#hVI0qfdztGfuAoMgG0oz

Pretty basic, although I know my view on toughness is a little isolated. I just feel like you'll need all the hps you can get when you first ding 80. In fact, I actually put more points in there when I was first pvping, so see what you think and take it from there.

Take Totem of Wrath on all shaman and glyph it. At low spell power levels this talent/glyph is unbeatable imo. This goes for pve as well.

Shaman pve: http://www.wowhead.com/?talent#hEh0qcdItGfzVo0xxIo

One thing that I do that not everybody does, I take a lot of the mana reducing/regen talents. The reason is that a) I don't like to sit around after battles drinking, and b) I like to run 4 elemental shaman rather than 3 elemental/1 resto because I feel that it's more dynamic and simpler. Some fights can be pretty healing intensive, so having good mana regen is a must for this choice.

You might also notice that I'm skipping some of the lava burst focused talents. Reason is that LB spam is almost equal in my gear (both RAWR and dummy), and, again, SIMPLE. I can't stress enough how important keeping things simple is, especially as you get into the harder content and/or pvp. So lately I've been just LB spam in pve.

Paladin: Just a standard tanking build, visit tankspot.com, elitistjerks.com, etc.

1 priest/4 mages is an awesome pvp combo, but after playing a shaman team I just missed the healing (when my priest was CCed) and the chain armor. A rogue would open on one of my mages and like 3 shot it with little time for me to react. Part of that was gear, but there was a lot of other things too: stacked tremor totems, 4x grounding totems. So yeah, can be done (and has), and it's a fun team, but I found it kind of frustrating.