The toxicity of carbon monoxide in terms of its interaction with haemoglobin
Carbon Monoxide and dioxygen both reversibly bind to the iron atom in hemoglobin.  

The two molecules compete for the same binding site.  

So if both $\ce{O2}$ and $\ce{CO}$ are present, some of each will bind, but for a given amount of $\ce{O2}$, less $\ce{O2}$ will bind if $\ce{CO}$ is present. The affinity of the Fe for $\ce{CO}$ is much greater than for $\ce{O2}$, so a lower concentration of $\ce{CO}$ results in a given saturation level of hemoglobin compare to $\ce{O2}$.

The same would be true for cyanide which is isoelectronic with carbon monoxide.  

A more complete explanation needs to go into the cooperation between the four hemoglobin subunits.  $\ce{CO}$ bound to two of the four subunits causes $\ce{O2}$ to being too tightly bound in the other subunits.  That the oxygen can not be released from the hemoglobin, is another aspect of toxicity.