Firstly, recall that American-style option may be exercised at every time point. If you model the stock as a tree, you need to check at every node, whether the investor would like to use his/her right of early exercise.
So, how do you price derivatives in general? You build the tree for the stock price and then a second tree via so-called backward induction: You begin with the terminal payoff and work backwards through the tree by computing the ``discounted expectation'' of the future nodes. In the end, this gives you the price of a European-style option.
For American-style options, you must also take early-exercise at every node into account. As you probably know, if the stock price has fallen sufficiently, you may wish to exercise your put option early. Thus, at every node, you firstly compute the so-called continuation value (discounted expectation of future nodes as above) and the immediate payoff which you would obtain when you exercised the option at this node. Which value do you choose? As Alex said, the maximum of both. Thus, you only exercise the option when the immediate payoff suceeds the value of continuing to hold your option.
You wonder whether the price process of American options is perhaps not fair. Actually, it really is not fair. For European-style options, we can find a price process which is a martingale (model for fair games) but for American-style options, the price process is a super-martingale which is indeed, not a fair game. (you may want to read about Snell envelope)