If the grease fittings are goobered up with rust, phosphoric acid (such as Naval Jelly) will selectively dissolve the iron oxide (rust) but won't hurt the steel fititng. In theory, this should also "passivate" the steel fitting so it won't rerust as easily -although I wonder how well this really works.

First "degrease" the fittings by spraying them out with carb cleaner to get the grease off the rusty areas. You can't derust a part unless it's clean.

If you can't think of an easy way to get Navel Jelly (a gel) through the fitting (such as with an extra grease gun), you could also use any of several liquid (water-like viscosity) rust dissolvers, containing phosphate (zinc phosphate usually), phosphoric acid, hydroxide (main component of Drano), or similar and just soak the fittings in this solution for a couple hours.

The phosphoric acid or hydroxide solution, be it a liquid or gel, should be rinsed completely out of the fittings with water, then followed by a spray of carb cleaner to remove all residual water. Protect the fitting from rerusting with a shot of oil or grease.

The chemical reactions are explained here (note that acetic acid or vinegar will also work, similar to phosphoric acid):
http://www.corrosion-doctors.org/Experiments/iron-products.htm

If you're like me and hate to replace parts, as cheap as they are, it's worth a try anyway. I also happen to have lots of chemicals around.