Oxygen has very low solubility in water, which decreases with temperature. Haemoglobin binds iron atoms, which bind oxygen molecules, allowing storage of oxygen by the protein. IIRC, this increases the oxygen carrying capacity of blood approximately 60 to 70 times.