Excursion into simple coordination chemistry: Bonding, backbonding and simple orbital schemes
Please refer to Breaking Bioinformatic’s answer for the MO scheme of carbon monoxide, it is very helpful. You might also look at the orbital pictures in this answer by Martin. Carbon monoxide can bind to metal centres via a σ coordinative bond where the HOMO of $\ce{CO}$ interacts with metal orbitals and also by the π backbonding, Breaking Bioinformatics mentioned. I’ll start by touching the σ bond so we can later better understand the π bond. In figure 1 you can see the molecular orbital scheme of a complex composed of a central metal ion and six ligands that donate in a σ manner exclusively.
Figure 1: Molecular orbital scheme of an octahedral complex with six σ donors around a central metal. Copied from this site and first used in this answer of mine. Metal orbitals are 3d, 4s, 4p from bottom to top; ligand orbitals are of s-type.
You will notice that figure 1 contains the irreducible representations of the orbitals beneath them. Orbitals can only interact if they have identical irreducible representations; otherwise, their interactions will sum up to zero. We can see that the metal d orbitals are split up into a $\mathrm{t_{2g}}$ set and and $\mathrm{e_g}^*$ set. This is the effect of σ bonding and why it stabilises the entire entity.
π bonding can only occur if the ligands have available orbitals of π symmetry. The 2π orbitals of $\ce{CO}$ are a nice example, but one could also simply assume a halide with its p-orbitals for the same effect. Further down in the internet scriptum I originally copied the picture from, you can see a set of two pictures that introduce p-orbitals. Twelve ligand p-type orbitals will transform as $\mathrm{t_{1g} + t_{1u} + t_{2g} + t_{2u}}$, thus a further stabilising/destabilising interaction is introduced for the $\mathrm{t_{2g}}$ orbitals. Due to the $2\unicode[Times]{x3c0}^*(\ce{CO})$ orbitals being similar in energy to the metal’s $\mathrm{t_{2g}}$ and empty, they can stabilise the former well, creating a possibly strong stabilisation for the overall system. Since this is an interaction of two orbitals creating both bonding and antibonding orbitals, and since the resulting molecular orbital is filled with two electrons that stem from the metal centre this is termed π-backbonding.
The binding mode of carbon monoxide to haemoglobin
After this extensive background discussion, it may be clear that $\ce{CO}$ is generally a good ligand. For reasons I didn’t go into, a carbonyl complex of metal ions isn’t that stable, but a single carbonyl ligand will almost always be beneficial. Such is the case for the porphyrin-iron(II) system that forms the heart of haemoglobin: The central iron(II) ion is coordinated well from five directions (four from the porphyrin ring and one histidine of haemoglobin) and has a weakly bound water atom in the ground state in its sixth coordination slot, sometimes displaced by a distal histidine. Carbon monoxide can diffuse in and bind very well to this system, displacing the weakly bound water and histidine. In fact, isolated haem can bind carbon monoxide $10^5$ times better that it can oxygen.
This is something that nature could not really inhibit, because it is based on fundamental properties, but also something nature didn’t really care for, because the natural concentration of carbon monoxide is very low, and nature rarely had to deal with it competitively inhibiting oxygen binding to haemoglobin.
The binding mode of oxygen to haemoglobin
Oxygen, the $\ce{O2}$ molecule, is an absolutely lowsy σ donor — especially when compared to $\ce{CO}$. Its molecular orbital scheme is generally that of carbon monoxide except that it is entirely symmetric and two more electrons are included: They populate the 2π orbitals to give a triplet ground state. These orbitals are now the HOMOs and they hardly extend into space in any meaningful way — plus the still existant lone pair on each oxygen atoms is now at a much lower energy and also does not extend into space and thus cannot bind to a metal centre in a σ manner.
What happens here is rather complex, and the last lecture I heard on the topic basically said that final conclusive evidence has not yet been provided. Orthocresol discusses the different viewpoints in detail in this question. The diamagnetic properties of the resulting complex are, however, unquestioned and thus one must assume a singlet ground state or one where antiferromagnetic coupling cancels any spins at molecular levels. Since the ground state of haemoglobin has a high-spin iron(II) centre and the ground state of oxygen is a paramagnetic triplet, it makes sense to assume those two to be the initial competitors.
Professor Klüfers now states the steps to be the following:
Iron(II) is in a high-spin state with four unpaired electrons;
Paramagnetic triplet oxygen approaches and one of its $\unicode[Times]{x3c0}^*$ orbitals coordinates to the iron(II) centre in a σ fashion.
This induces a high-spin low-spin transition on iron and slightly reorganises the ligand sphere (pulling oxygen closer to the iron centre). We now have a low-spin singlet iron(II) centre and a coordinative σ half-bond from oxygen. We can attribute that electron to the iron centre.
Through linear combination, we can adjust the spin-carrying σ orbital and the populated iron orbitals so that an orbital is generated which can interact with the other $\unicode[Times]{x3c0}^*$ of oxygen in a π fashion.
We thus expect an antiferromagnetic coupling and an overall state that can be described best as $\ce{Fe^{III}-^2O2^{.-}}$ — a formal one-electron oxidation of iron to iron(III), reducing oxygen to superoxide ($\ce{O2-}$).
If the spin-carrying orbitals are all treated as being metal-centred, we gain a $\ce{Fe^{II}-^1O2}$ state.
(Content in the link I quoted from are in German; translation mine and shortened from the original.)
Only due to the complexly tuned ligand sphere and also due to the stabilising high-spin low-spin transition (plus reorganising) is oxygen able to bind to iron at all. The distal histidine further stabilises the complex by a hydrogen bond, alleviating the charge slightly. It is to be assumed that nature did a great deal of tuning throughout the evolution since the entire process is rather complex and well-adjusted for collecting oxygen where it is plentiful (in the lungs) and liberating it in tissue where it is scarce.
Comparison of the oxygen and carbon monoxide binding modes
The simpler picture I drew above for carbon monoxide is not correct. Inside haemoglobin, carbon monoxide also binds in an angular fashion as if it were oxygen — see bonCodigo’s answer for space-filling atom models. This is because the entire binding pocket is made to allow oxygen to bind (as I stated) thus attempting everything to make oxygen a comfortable home. Carbon monoxide is rather strained in there, its binding affinity is reduced by a factor of $1000$. However, since we started with a binding affinity difference of $10^5$, carbon monoxide can still bind $100$ times better than oxygen can.
Summary
Carbon monoxide is generally a good ligand that can bind to metal centres well.
Oxygen is generally a poor ligand.
Nature did everything to make oxygen a comfortable home in haemoglobin.
In doing so, the binding pocket became substantially less comfortable for $\ce{CO}$.
But since carbon monoxide was so good and oxygen so poor to start with, the former still binds better than the latter.
Nature didn’t really care, because individuals seldomly come in contact with carbon monoxide so the collateral damage was taken into account.