Some recent work has indicated that Nitric Oxide can be carried on molecules of Hemoglobin -- specifically the relaxed form, oxyhemoglobin, can form S-Nitrosohemoglobin by reaction with beta-Cys-93. The article by Stamler et al. was published in Science, v. 276, pages 2034-2037, the June 27, 1997 issue. It is titled "Blood Flow Regulation by S-Nitrosohemoglobin in the Physiological Oxygen Gradient."
The Nobel Prize announcement gives a good overview of NO activity and the history of its discovery. And the Nitric Oxide Home Page, while a little daunting, is a good clearing house for information about NO. Below are a few references from that page.