There are several physical versions of this puzzle:
(Elephant) Spinout, by thinkfun:

The Brain, by Mag-Nif:

and the traditional Chinese Rings puzzle:

The solution is based on the Binary Gray Code. At any moment at most 2 moves are available, so there is never really any choice - you can only move forwards to the solution or backwards away from the solution. With the physical puzzles above, there are two moves available at the start so you can start off in the wrong direction.
With the coin puzzle as described there is only one possible first move, so you will always start in the right direction, and if you never reverse direction by undoing a move, it will eventually be solved. It would have been more interesting if the coins started all tails, and the aim was to get all heads. Then you could flip either the first or second coin as a first move. The correct first move is then:
the first if there are an odd number of coins, the second if there are an even number of coins.
Starting at all heads, you can run through all $2^n$ configurations in $2^n-1$ moves, ending with the configuration where all but the last coin is heads. The all-tails position is two-thirds of the way through, so it takes $\lfloor \frac{2^{n+1}}{3} \rfloor$ moves to solve the puzzle.
You can find more information on my website.