Bruce Schneier points to a paper on the statistics of coin-tossing. Summary of the summary: not random. One item:

If the coin is tossed and caught, it has about a 51% chance of landing on the same face it was launched. (If it starts out as heads, there’s a 51% chance it will end as heads).

In retrospect, this is not all that surprising. It’s good to keep in mind.

Commenter Michael Ash suggests a mechanism for compensating for the bias:

Flip the coin twice. If the first one is heads and the second tails, take one choice. If the first is tails and the second heads, take the other choice. If you get the same face both times, start over. This last part is key: you must start over and flip two more times, and keep flipping in pairs until you get two different faces. It’s not enough to just flip in sequence until you see a change. You have to completely discard the result and begin anew.

This works (I think), but only if the two flips are independent of each other, a non-trivial assumption.