The performance of muon reconstruction in CMS is evaluated using a large data sample of cosmic-ray muons recorded in 2008. Efficiencies of various high-level trigger, identification, and reconstruction algorithms have been measured for a broad range of muon momenta, and were found to be in good agreement with expectations from Monte Carlo simulation. The relative momentum resolution for muons crossing the barrel part of the detector is better than 1% at 10 GeV/c and is about 8% at 500 GeV/c, the latter being only a factor of two worse than expected with ideal alignment conditions. Muon charge misassignment ranges from less than 0.01% at 10 GeV/c to about 1% at 500 GeV/c.