I would figure out how much you want to spend and go from there. I would think re-powder coating would run about $600( I was quoted $275 for a bumper alone), it might be cheaper to buy the powder coating machine and paint, apply it yourself and opnly pay a shop to bake it on. A commercial spray on truck liner would be about the same price as powder coating. Duraback is a good DIY coating but at $50+ a gal. for black ($120 for colored) it gets pricey, the Herculiner doesn't wear well, and it fades withion about 6 months, and the Duplicolor is a bit soft for bumpers and berf bars. Rustoleum has a truck bed kit for DIY's, you might look into it.

I think using rustoleum primer and paint would be the easiest way of going, don't use the spraycans, buy it by the pint, this way you can put on thin coats and build up the paint. You will want to put some type of paintable undercoating on the bottom and leading side of the nerf bars to help reduce chipping caused by rocks(unless you are running mud flaps).