Well, they DID say, "the Orcs have a charismatic new leader"...
In my world, paladins are not Arthurian chevaliers, they are the fighting force of a religion. Hence, they for the most part mirror the attributes of the deity and the deity's moral codes of cunduct.
The paladins of the Night / Moon / Dreams deity go out primarily at night. They have an elitist attitude, for they feel that they alone have the fortitude to go forth and hunt evil in its own element - the night. They are primarity stealthy; they are the ones responsible when you hear a noise at night, but by the time you get a light and go check, there's nothing there... they have already done their work.
Other paladins have other descriptions, other methods, but all are a martial aspect of their deity made manifest on earth.