We let ours go au natural (but it is all cast iron):
View attachment 198609
It's looked like this for the 15 years we've had it out in the weather. Sometime before we acquired it the previous owner had given it a coat of rust colored paint. Welding a sacrificial zinc anode in an out of the way place would slow the rust down. Some steel/iron is better than others at getting and maintaining a rust patina. I think on an outdoor stove, trying to prevent all rust is an exercise in frustration.
If you want it painted I would use Ospho first. It's just a dilution of phosphoric acid. The phosphate in the acid converts the rust, ferric oxide (Fe2O3), into iron phosphate (FePO4) and water in the reaction:
Fe2O3 + 2 H3PO4 ® 2 FePO4 + 3 H2O
What was rust will now be a well-adhered hard black coating. If not protected, it will rust again when wetted but this is a good final prep for rusted metal before paint or primer. I've never tried this on anything that gets as hot as a woodstove but it typically extends the life of the paint many times.
Remove all loose rust with a wire brush. Wipe down with a damp terrycloth rag. Put down something to protect the surface underneath. Use a cheap brush with natural bristles to stroke the dilute phosphoric acid up the rusted surfaces. They will turn black almost immediately. When it is almost dry repeat once or twice to ensure all the rust is converted. After the final dry it is ready for primer or paint. But most stove paint will not handle the hottest portions of a well fired woodstove anyway. But it might look better than what you have.