Comming from BFA retail i don't remeber how classes played in Wotlk so i decided to make this post. I've been playing healer for the past 7 years and i've always played both sham and pala and now i can't choose. I'll be playing the Icecrown realm so i wondered wich one is more sought after. I heard the realm is flooded with paladins which would make finding groups and guilds harder. I also consider offspec options so take that in mind too. Thanks!
Shammies are great, flexible healers, Bloodlust/Heroism which means ez raid spots, but their DPS offspecs aren't as... attractive (not unviable, but they're not generally top dps material, and so you see them VERY rarely).
Paladins are dime a dozen, yes, but you do have an advantage of all three available specs being very relevant endgame, which makes it a bit more flexible if you decide to change your mind somewhere along the line.
That said, tanks > healers > dps in terms of demand all over the board, so you shouldn't have too much problem finding raids either way.
if you consider also arena pick hpala, a lot easier to find good dps, also its better option in world pvp and small battlegrounds like wsg/ab
as hpala i can laugh at average smourne user, as rshaman even braindead smourne can burst me down ;D