I feel sandpapers, and steel wools should be a last resort. They're going to scuff up the blade and make it look awful.
Try removing them by chemical means. Try using a mild polish like Brasso, or Novus. It has worked for me without leaving any marks or scars on the blade.
Flitz will work too but it is a bit more abrasive. It will give the blade a real nice sheen but may scrub off stamped logos.
Other mild solutions are household calcium/lime/rust removers. Available at hardware stores.
If it is medium rust, try diluting some automobile rust remover and rubbing it gently with a soft cloth. Careful, since this stuff is corrosive so it can stain your blade if you use it full strength.
Heavy rust: get the sandpaper, and steel wool out!