Define a person's unhappiness as one less than the position in their ranking of the person they paired with. If someone is not paired, define their unhappiness as N, where N is the number of men and the number of women being paired.
For example, in a set of 10 men and 10 women, a women paired with her 1st choice man has unhappiness 0. A man in that set not yet paired has unhappiness 10.
The key to understanding Gale-Shapley is female unhappiness (in the version where the men propose to the women...if you do it with women proposing to men, then male unhappiness is the key).
When the algorithm runs a man through the gauntlet and his proposal is tentatively accepted by a women, her unhappiness decreases (and no other woman's happiness changes). Hence total female unhappiness decreases every round. Total female unhappiness is a non-negative integer, and it is bounded by N^2 where N is the number of females. This shows that the algorithm must terminate, and must do so in at most N^2 rounds. It is also easy to see that the algorithm only terminates when all men are paired. Thus, we can conclude that the algorithm will produce a final pairing in which everyone is paired, and it will do this in at most O(N^2).
Consider any man, M1, paired by this algorithm with woman W1. Because men propose in order of their rankings, M1 has already proposed to every woman he prefers over W1. Either they were rejected (meaning those women were already paired with men they prefer over M1) or they were tentatively accepted but then later he was jilted when someone better came along. From this, we see that the pairings produced by the algorithm (including the partial pairings after each round) are such that no man is willing to cheat on his currently assigned partner. Hence, they are stable.