Stainless steel rusts from iron/carbon steel contamination. So don't use steel wool or a wire brush unless it is stainless steel too.
Green scotch brite pads work well for surface rust. when done scrubbing, clean with acetone or mineral spirits then use a carnuba paste wax on it.