In contrast to CO, which bonds to Fe2+, CN- has a stronger affinity to Fe3+. This can be understood with typical complex chemistry. The main reasons may be that negatve cyanide will be attracted to the stronger positively charged Fe3+ and that it is a weaker π-acceptor. The consequence is that cyanide doesn't bind to hemoglobin but just to cytochrom c oxidase the fourth and last protein complex of the respiratory chain inside the mitochondrion. There it inhibits any oxidative degradation of nutrients. Someone poisended by cyanide will appear red since the oxygen stays on the hemoglobin instead of being used up by the respiratory chain.
The clean way for detoxification is the use of hydroxycobalamin (B12). It binds to CN- in a stable complex. If this expensive substance is not at hand, detoxification can be done with nitrite. It oxidates hemoglobin to methemoglobin. And cyanide is bonded to its Fe3+. The danger of this procedure is that methemoglobin doesn't carry oxygen. So nitrite has to be carefully dosed.
Since cyanide is found in nature (almonds, seeds) it makes sense for the body to have its own detoxification system. The enzyme rhodanase makes thiocyanate out of cyanide. You can see a few helices, random coils and two sets of parallel β-sheets. The active Cys-247 residue is shown left of the center.
The active group is Cys-247, changed to a disulfide. It gives a sulfur atom to cyanide, producing thiocyanate. The disulfide is regenerated with thiosulfate.
In fact the protein is not a pretty thing like shown above but just a bunch of atoms crowded together.
The active cystein residue can be seen as a yellow spot above the center. It is remarkable that it is visible in a spacefill model even though it is right inside of the protein. This of course makes sense because the group has to be accessible in order to be catalytically active.
The structure was taken from RSCB Protein Data Bank. The images were drawn in PyMOL.
I made one more picture which I think looks kind of cool. This is the enzyme inside a transparent surface.