THIS IS STILL IN PROGRESS (10/24/2011)
Markov chain Monte Carlo (MCMC), and its variant, multiple chain Markov chain Monte Carlo (MCMCMC) are used increasingly in phylogenetics but not well understood. Here's a stab at a tutorial.
First, unpacking the terminology. A Markov chain is just a process where your next position is a function of just your current position, not previous positions (it's a memory-less process). Imagine a the path a taxi may take over the course of a day. Perhaps it starts at an airport and then picks up a fare to the train station, picks up a fare back to the airport, then to the museum, then to a hotel, then to the airport, then to the train station. The sequence of steps is A -> T -> A -> M -> H -> A -> T. Each time, a new person is getting into the cab: the passenger doesn't care where the cab has been, only where they want to go. Note that the cab itself doesn't have to spend an equal amount of time at each location, and the chances of going from each location to each other location do not have to be equal (in our example, there seems to be a lot more travel between the airport and train station than between other destinations). All that is required is that at any step, the chances of going to a particular location are based only on that location (i.e., the chance someone at the airport wants to go to the train station is 2/3, independent of whether the cab arrived at the airport from the museum or the train station). The path a particular passenger takes across the city by cab will not be a Markov chain: if they arrived at the airport, and then went to the train station, their next destination is more likely to be the hotel than the airport again. But at the end of their stay, the next time they are at the train station they are more likely to be going to the airport than back to the hotel.
Monte Carlo methods are named after the Monte Carlo casino in Monaco. If they were being named today, at least to an American audience calling them "Vegas-style" might make more sense. Imagine the game of battleship, where boats of varying lengths (think vectors of length between 2 and 5) are placed on a matrix, such that each boat is horizontal or vertical and does not overlap any other boat. What is the chance, when boats are placed randomly on the board starting with the shortest boat, that the longest boat (the aircraft carrier) is entirely contained in one of the rows or columns on the edges of the board? If it were just one boat on the board, calculating this by hand might be feasible, but it becomes difficult when the interaction between boats must be taken into account. The Vegas-style solution is to avoid doing math and just set up a bunch of boards at random. The proportion of times these simulations result in the desired condition (an aircraft carrier lurking on the margin) is an estimate of this true probability. All you do is simulation from a model (how you arrange boats randomly on the board) to estimate a parameter.
We'll come back to multiple chains.
Markov chain Monte Carlo integration (MCMC) is a way to estimate the shape of a landscape by stumbling around based on some model of you move (Monte Carlo) where the model doesn't care where you've been in the past (Markov Chain).
INSERT HAT EXAMPLE