The existing answers explain, chemically, why hemoglobin ($\ce{Hb}$) binds $\ce{CO}$ much more strongly than it does $\ce{O2}$. In reading them, you might get the idea that nature evolved $\ce{Hb}$ to bind $\ce{O2}$ as well as possible, and simply didn't account for $\ce{CO}$.  The latter is likely true, but not the former.  

In fact, nature didn't evolve $\ce{Hb}$ to bind $\ce{O2}$ as strongly as possible.  Think about how $\ce{Hb}$ operates: It doesn't merely need to bind $\ce{O2}$; it also needs to be able to *release* it.  Yes, there is a pH/ $\ce{CO2}$/ $\ce{2,3 BPG}$-induced conformational change in  $\ce{Hb}$ that facilitates this, but there are limits to how much the binding affinity can change as a result.  Thus $\ce{Hb}$ can't bind $\ce{O2}$ too strongly and still fulfill its biological function. Instead, the affinity of $\ce{Hb}$ for $\ce{O2}$ must be finely balanced between binding and release.

Consequently, it is not surprising that a foreign substance ($\ce{CO}$), not present in appreciable quantitites when $\ce{Hb}$ evolved, can outcompete $\ce{O2}$. The best analogy to $\ce{Hb}$'s affinity for $\ce{O2}$ is Post-It Notes.  These use an adhesive that sticks, but sticks weakly, so it can release easily when needed.