[Image taken from lscheffer.com, who also has a nice analysis.]
In my own words, a Markov-chain is a series of random states. A trivial example might be flipping a coin; the coin is either in a state of "heads" or "tails" and has a 50% chance of changing state with each flip. It can get more complicated, with the probabilities of changing to a different state dependent on the current or even (correct me if I am wrong) previous states. A state which ends the series (if any) is called an absorbing state. In my recent Netrek post the number of planets a team controls would be the state, and the absorbing state would be one team conquering all the planets, thus ending the series and the game (oversimplified, but true).
Candyland is a Markov-chain if you reshuffle the deck of cards after every draw. Each square (rhomboid?) on the board represents a state, and players advance randomly towards the end of the game. Reshuffling is required so that the probability of changing states remains independent of previous card-draws (if you were wondering). There is a nice summary and history of the game itself here.
Speaking of fine work, Greg Costikyan wrote about this a few weeks back, and it has traveled far in the blogosphere. The really interesting part here is (for me) the discussion of whether or not it really is a game; all moves are random, so if the player doesn't actually do anything is it really a game? My answer: Yes. Not the most interesting game we may ever play by any means, but most definitely a game. Games where players make decisions and enact strategies are more difficult, and for most, more interesting.
I should not end without mentioning an older game that is a Markov-chain to start with - no reshuffling required - known to most as Snakes and Ladders.
[Image from DKimages]