"A paladin who ceases to be lawful good, who willfully commits an evil act, or who violates the code of conduct loses all paladin spells and class features."
I offer up the following five criterion for determining when a Paladin should fall. If a Paladin meets all five of these criterion, he should fall. If a Paladin meets the first two, and at least one of three, four, or five, he might fall. If a Paladin does not meet both one and two he should not fall, regardless of all else.
1: Did you warn him?
The fall of a Paladin should never come as a surprise. It is the DM's duty to warn the Paladin of any wrongful course, should the player (if not the character) be unable to see it. Pathfinder is a cooperative game that is about having fun. Players will have a bad time if they feel that their powers are taken away without warning or apparent reason. The DM must warn the Paladin that he is stepping down the wrong path, and perhaps suggest a better one. If you forgot to tell the player that he may lose his paladin abilities, then his character should not fall.
However, if you told a Paladin that his actions were likely to lead him down the path of darkness, and he took them anyway, then tally one against the Paladin. However, take a second to consider what exactly an act worthy of falling is...
2: Was there an obviously better alternative?
Every once in a while, a DM will place a paladin, intentionally or not, in a situation without a clear correct path. Let's take the most basic possible example. There are two children trapped in a burning building. The Paladin only has time to save one. Either way the Paladin will have the death of a child on his hands, and so he should not be penalized for choosing one or the other. There is no better alternative, so the Paladin should not fall.
Now, let's say that the Paladin has in his possession a wand of create water capable of putting out the blaze and saving both children. However, the player or the character are unaware of the nature of the wand, and so does not use it. This wand is not an obviously better solution, as the Paladin is unaware of it, so the Paladin should not fall.
For the sake of argument, lets say that the Paladin is again faced with the burning building. Instead of saving either child, he decides now would be a wonderful time to pull out his bag of endless marshmallows and make a s'more. There is an obviously better solution, so this may be grounds for falling.
3: Was his act unlawful?
Pathfinder describes the relationship between lawful and chaotic:
"Lawful characters tell the truth, keep their word, respect authority, honor tradition, and judge those who fall short of their duties. Chaotic characters follow their consciences, resent being told what to do, favor new ideas over tradition, and do what they promise if they feel like it."
Let's consider an example. The Paladin Charity believes that she should give money to the poor. Charity finds herself in the Land of Nice, where giving alms is mandatory. She gives half her money to a beggar. This is clearly a lawful act, as she is following both the law of the land, and her own personal code.
Next, Charity wanders over to the Land of Mean, where it is illegal to give money to the poor. The King of Mean is a wealthy jerk who kicks kittens every morning. Charity decides to follow the rule of law, and she refrains from giving alms. If Charity is the kind of Paladin who favors rule-of-law, then this is perfectly acceptable behavior. If Charity is the kind of Paladin who favors personal-code, then this might be grounds for falling.
After spending a few weeks in Mean, Charity has a change of heart, and wants to give money to the poor. However, all of her money has been taxed away. She decides to steal from the King of Mean, and give the money to the poor. If Charity is the kind of Paladin who favors personal-code, then this is wonderful. If Charity is the kind of Paladin who favors rule-of-law, then this might be grounds for falling.
After successfully sneaking in to the castle, she comes across the treasure trove. The mounds of gold open her eyes, and Charity decides to take it all for herself. This is clearly an unlawful act. She is breaking the laws of Mean by robbing, and she is breaking her own personal code.
4: Was his act "un-good"?
"Good characters and creatures protect innocent life. Evil characters and creatures debase or destroy innocent life, whether for fun or profit."
Some acts are clearly good (such as petting a puppy). Some are clearly evil (such as killing a puppy). Most of the confusion comes from greater good and immediate good. Find out if the paladin favors greater good over immediate good. Often, these two ideas will be in conflict, and when they are make sure to favor the paladin's reading of it.
Paladin Smartz goes after a werewolf who has been terrorizing a village. He tracks the werewolf back to its lair, and finds that the werewolf is a poor, defenseless boy who cannot control himself. Luckily Smartz can remove the curse. This is clearly a good act. He is serving the immediate good by saving the boy, and he is serving the greater good by protecting the townsfolk.
However, there is some bad news for Paladin Smartz. Remove curse does not work. Smartz raises his sword to strike the boy down. If this is a greater good Paladin, then this is the right move. Killing the boy will prevent any further attacks on the village. However, if this is an immediate good Paladin, then this may be grounds for falling, as killing an innocent boy certainly feels like an evil act.
Paladin Smartz slowly lowers his sword. He cannot kill the boy, but his adventure would have no room for him. Instead, he will bring the boy to the town jail, and force the town to work on his cure. If this is an immediate good Paladin, then he has fulfilled his objective. The innocent boy is not dead. However, if Smartz is a greater good Paladin, this may be grounds for falling. He is endangering the lives of every civilian by letting the werewolf live.
The conundrum is too much for the Paladin. He slays the boy, then returns to the village. Smartz is angry at the mayor for placing him in such a delicate position, so he returns to town hall and slays the mayor. Then all the witnesses. Then everybody else in town. This is clearly an evil act, as it serves neither the greater good, nor the immediate good.
5: Was his act against his God?
Paladin Hare worships BunnyLord, Lord of Bunnies. He favors rabbits, hates oozes, and is pretty relaxed about out-of-wedlock hanky-panky. When Hare is faced with a possessed rabbit, he chooses to capture the creature and perform a complex exorcism rather than simply kill it. When he is given the choice between killing dragons and killing oozes, he kills oozes every time. And when he finds his wife in bed with the mayor, he lets them both off with a warning instead of taking more serious action. Paladin Hare is a great follower of the Bunnylord.
Paladin Roast also worships the Bunnylord, Lord of Bunnies. When Roast is faced with a possessed rabbit, he slays the beast to prevent further damage. When he is given the choice between killing dragons and killing oozes, he goes after the red dragon that has been causing more damage than any ooze. And when he finds his wife in bed with the mayor, he takes them both to a court of law for adultery. Even though none of these acts is non-good or non-lawful, the Bunnylord may still be displeased. Probably not grounds for falling, but the Bunnylord may have a stern word with Paladin Roast.
A Paladin can be many things, and it is important to know exactly what a Paladin is before passing judgement. To wrap up, let's consider the following example.
Paladin Triky is greater good paladin, who follows a strict code of "destroy all demons" and worships the BunnyLord. He is faced with a possessed rabbit who has been terrorizing the villagers. But the villagers have been unable to kill it due to strict no-poaching laws. He decides to destroy the rabbit as quickly as possible. Should he fall?
Well, you may want to ask Triky. Triky was preserving the greater good by saving the villagers, even at the expense of the life of an innocent bunny. He also broke the no-poaching law in favor of his own personal code. However, that's all consistent with who Triky is as a Paladin. True, he went against the BunnyLord's wishes, but with good reason. Paladin Triky should not fall for killing the bunny.
Paladin Conflikt is an immediate good Paladin who follows the law of the land and worships the Oozelord. He decides to save and cage the bunny, wasting time and resources searching for a cure. Should he fall?
Well, you may want to ask Conflikt. Conflikt was favoring the immediate good by saving the bunny, even at the potential expense of all those around him. He preserved the no-poaching law, even against the OozeLord's wishes. Paladin Conflikt should not fall for saving the bunny.
Here's the take away: What might make one Paladin fall is the right choice for another. Know your player's Paladins. Don't place them in unwinnable situations, or, if you do, don't penalize them. And above all, let them know if a certain action will lead to a fall.