The axiom of choice, broadly speaking, says that no matter what kind of collection you have, you can always pick one and only one element of each set in the collection.
It is intuitive in the case of finite collections. Suppose you have $n$ color-coded bags, each containing $m$ numbered balls, without repetition. Then from each bag you can take one ball from each and make a new set of representatives of each set.
Now for the countable collection. Suppose for each colored bag we also numbered them "up to infinity". The axiom of countable choice says that we can still pick one ball from each bag and make a new set.
And now comes the more abstract case, of uncountable collections. Drop the numbered bags; your bags are still color-coded, but you allow them to have any color. Literally, any; there's a bag for every visible wavelength you can come up with, to infinite precision (doesn't matter if the difference is discernible or not). The full axiom of choice says that there is still a way to pick one ball from each bag (but doesn't say how).
Back to the problem, you need to recognize that the number of possible sequences is uncountable-infinity.
From all those sequences, the prisoners need to sort them out. So, the $n$-th prisoner sort the possible sequences he can be with the following rule:
If from the $n$-th hat the sequence doesn't change anymore, they belong to the same class. That is, if the hats don't change beginning from my hat, they're into the same class.
That is, suppose you have $RGRGRGRGRG...$, $GGGGRGRGRG...$ and $RRRRRGRGRG...$. Notice that beginning from the 5th hat the sequence is the same, so they belong to the same class for the 5th prisoner. Of course, the first prisoners will have fewer and "larger" classes than the ones behind them.
The axiom of choice implies that from each class they can pick a representative. So, suppose they agreed on a representative for every single class. Note that, by fixing a sequence from each class, they're actually deciding which color they'll call their hat, based on the outcome of the people in front of him.
Let's line them up now. Note that the actual sequence they were put into is inside a class for every prisoner.
The first, well, has only one class with all sequences. Poor him, but he was really unlucky to be picked among infinite prisoners. He calls out the predetermined sequence and hopes for the best.
The second prisoner has seen what happened with the first one, and calls out his color based on that.
The third eliminates all classes that didn't match the new outcome, and calls out his choice for the 3rd.
And on and on and on.
Now, remember that every sequence was in a class, including the actual one? That means that after the $m$-th prisoner the actual sequence will be in all subsequent classes, however large $m$ might be. So at most only $m$ prisoners will die.
Note that if the $n$-th prisoner was the first one that called his color right, you can still have $m\neq n$, since the $n$-th representative might not be the actual sequence, or the $n$-th prisoner just really got lucky and chose the right color. But $m$ is certainly finite, because of how we constructed our classes.