Hyperventilating causes a rise in plasma oxygen concentration and a drop in plasma CO2 concentration. People who are hyperventilating can pass out, although this may seem counterintuitive at first. The reason is because although hemoglobin saturation may be at 100%, it cannot release O2 to the tissues without some degree of CO2 present. In other words, CO2 decreases hemoglobin affinity of O2 at the tissue level. Hence, breathing into a brown paper bag will allow more Hb molecules to release their supply of O2.
Hb displays cooperativity, meaning that when one of its binding sites (there are 4 per hb molecule) binds to O2, it facilitates binding of O2 to the other three sites. This is why the dissociation curve is sigmoid shaped. A left-shifted curve signifies increasing affinity of Hb for O2 (at the tissue level), a right shifted curve signifies decreasing affinity of Hb for O2 (at the tissue level). The curve shifts to the right when you need more oxygen, i.e. exercising, etc. Byproducts of respiration are the major trigger for a rightward shift: CO2 (with concomitant pH decrease), and increased 2,3-bpg.
A couple other things to remember: myoglobin is left-shifted in comparison to Hb. Myglobin exists in muscle and must have a higher affinity for O2 in order to pick up O2 from the Hb molecules passing through the muscle capillaries. Also, fetal hemoglobin is left shifted. Just remember, you can't spell "fetal" without L-E-F-T.
One last thing: at high altitudes, the kidneys will produce the hormone erthropoietin to increase the number of red blood cells (i.e., to facilitate tissue oxygenation due to the lower O2 in the air).