Why is the cyanide ion toxic?
Cyanide is a pretty good ligand for coordination compounds. The electron pair on carbon (which, incidentally, also carries the Lewis structure’s formal charge) is located in the HOMO — much like as in $\ce{CO}$, whose molecular orbitals can be found in this answer by Martin (replace oxygen with nitrogen to arrive at $\ce{CN-}$) — making it a good Lewis base and a good &#x3c3; donor.

It is remarkable for being a strong-field ligand, i.e. one that often creates low-spin complexes even for 3d-metals (which generally prefer high-spin if there are no competing reasons for low-spin). While one could draw analogies to $\ce{CO}$ or even $\ce{NO+}$ whose &#x3c0;-antibonding orbitals are strongly Lewis acidic and participate in metal to ligand backbonding, it turns out that for cyanide the main reason is a high covalency of the metal–ligand-&#x3c3;-bond due to the relevant orbitals being very similar in energy. Thus, cyanide is unique in that it both stabilises higher oxidation states by being an anion and low-spin complexes due to its binding modalities.

One might think, in analogy to $\ce{K4[Fe(CN)6]}$, that cyanide preferentially binds to haemoglobin’s iron(II) centre and thereby inhibits oxygen transport, but that is in fact not the case as this centre requires a less-oxidised iron(II). Oxygen (due to the resulting redox-mechanism) and carbon monoxide are much better ligands for haemoglobin.

What cyanide does strongly inhibit is cytochrome c oxidase, the last enzyme in the respiratory cycle which collects electrons from four cytochrome c’s and transfers them to an oxygen molecule to create two water molecules:

$$\ce{4 Fe^2+-cytochrome~$c$ + 4 H+ + O2 -&gt; 4 Fe^3+-cytochrome~$c$ + 2 H2O}$$

This is done by a plethora of metal centres consisting of two haems, to cytochromes and two copper centres. I can’t tell you exactly which one, but there will be at least one which needs accessable iron(III) at some point in the catalytic cycle to which $\ce{CN-}$ can bind well and strongly inhibiting the catalysis of the enzyme.

Since the inhibited process is directly responsible for cellular respiration by transferring electrons to molecular oxygen (and being the only enzyme dealing with molecular oxygen in the respiratory chain), inhibition of this protein will cause the breakdown of the entire respiratory chain and lead to cellular suffocation.

Considering that an amount of $200~\mathrm{mg}$ can be toxic according to Wikipedia, and also considering that a human being contains some 10 trillion cells also according to Wikipedia, that’s still some 400 million cyanide ions per cell demonstrating the efficiency of binding and inhibition.

Note that popular antidotes also directly address the fact that cyanide is a strong ligand:


One antidote, hydroxycobalamin, presents the cyanide ion with a $\ce{Co^{III}}$ centre and a weakly bound, easily displaced hydroxido ligand. Hydroxide is displaced by cyanide creating cyanidocobalamin, a variant of vitamin B12 that the body has no problems dealing with. It is ejected via the kidneys. Injected into the circulatory system, it scavenges cyanides before they can enter cells.
Another antidote, also injected into the circulatory system, is 4-dimethylaminophenol (not to be abbreviated as DMAP to prevent confusion with 4-dimethylaminopyridine). It is an oxidising agent designed to oxidise haemoglobin’s iron(II) to methaemoglobin (containing iron(III)) thereby creating a much better acceptor for cyanide. Since there is a lot of iron(II) (a quick estimate with $8~\mathrm{mmol/l}$ gives $40~\mathrm{mmol}$ haemoglobin in human blood) in the blood for oxygen transport, small amounts of this can be sacrificed to capture cyanide before that reaches the respiratory cycle.