I did exactly this to my truck a couple years back. Dependent on where you live, and the amount of surface rust you have on the frame, I can suggest a couple of things that I did. I had a bunch of rust scales all over the frame. If you use a chipping hammer, you work your way around, hitting all of those, knocking them off, otherwise it is a near pointless task to paint, because those will always break loose over time and cause further rust. Then you use a wire wheel on a drill to clean up those areas. Next, you hit everything with a primer with a "rust converter" element to it. (Rustoleum makes a type like this) and finally, either a matte or gloss automotive black paint over everything dependent on what "look" you want.
You can paint everything under there without much worry. The exceptions are the exhaust system (you don't want to paint any of that), and around your brakes and their bleeders, rotors and such (You don't want any paint in there) You also want to take it easy around the plugs that allow you to drain/refill the front and rear differentials. You can paint those, but you don't want it thick where it makes it difficult to use those when you need to do fluid changes. You also really don't want to paint any part of the engine or transmission either. Unless you are OCD, you don't really need to cover anything or tape off on the underside, just avoid spraying on those things.
It is a pretty massive project to do it right, took me a few months to do it all right on my truck, working on it a bit by bit, as I had the time to devote to it. Good luck, and I hope some of this information helped!