Divine Focus (DF): A divine focus component is an item of spiritual significance. The divine focus for a cleric or a paladin is a holy symbol appropriate to the character's faith. The divine focus for a druid or a ranger is a sprig of holly, or some other sacred plant.
Every spell that has a component of DF requires a holy or unholy symbol to cast. Many, but not all, of a paladins spells require a divine focus. Without a holy symbol, the paladin can't cast those spells.
Clerics and Paladins seem to have a large number of spells that they can cast which don't require their holy symbol. However, I think (at low levels at least) only clerics will have spells which will be particularly useful.
You can restrict them more by binding their arms, but clerics (unless gagged) will still be able to use all 'command' spells.
Pathfinder Roleplaying Game, Adventure Path, Comics, Battles Case Subscriber
Of course, depending on where the PCs are being held and what's around (and also what god they worship), an improvised holy symbol may be possible. Not to mention that the Paladin is still a Full bab warrior with a variety of other magical effects...
Unlike a cleric, an oracle need not prepare her spells in advance. She can cast any spell she knows at any time, assuming she has not yet used up her spells per day for that spell level. Oracles do not need to provide a divine focus to cast spells that list divine focus (DF) as part of the components.