Er, depends what you want to do?
Both are plate classes. Both have, in most groups, the role of meatshield: be prepared to take a beating.
Warriors are straight melees. They are not very versatile but they are specialists : what they do, they do good. They have the best armors and weapons but you have to be willing to live without spells. That means you are very dependant on other people when it comes to staying alive. If someone goes down first in a group, it often is the Warrior as he's the designated one to get beaten up.
Paladins can take a good beating too, and they have some spells to help them annoy the mob (stuns, root) or help themselves and the group stay alive (the best healing of non-caster classes). They really shine against undeads. Compared to a Warrior, a Paladin is usually slightly less effective at taking damage but slightly more effective at dealing damage. Note also that Paladins must keep a GOOD alignment (or is it Good or Neutral? Can't remember...), else they suffer some penalties. That's not a big thing to be concerned about though.
As for demand for each class, *shrug*. You'll get people telling you one way and the other, but if you look at guild recruitment threads, you'll see that almost every class is wanted somewhere.