if it was me i'd probably get it down to bare metal where the rust is, put some POR15 black on (dont get that crap on your hands it lasts a week lol), repaint, then put the flares on like someone mentioned.
The problem is that they rust from the inside between the outer bed panel and the inner wheel well. You can't get to that area, other than through the 'drain holes', and treating the outside won't really help.
I don't know of a good way to fix it short of cutting the old bedside off, cleaning the foam out, and installing a new bedside. Still, without some way to treat the area between the bedside and the inner wheel well, it will eventually rust again. I suppose a really good undercoater with a long wand could get to it from underneath, going from the front and rear of the wheel house.
The 'cheap' fix is to install the fender flares and cover it up.
The problem isn't limited to Dodges, Fords and Chevys each have their own rust problems.
Dallas