I used a mildew-resistant primer and then an oil-based semi-gloss (found a great deal on the clearance rack!) and had them tint it sky blue for me. The coop was nearly done before the chicks arrived so it had weeks to air out but it didn't need more than a few days. And it's still pretty more than a year later! I also like that it's easier to clean than unpainted wood, it's sealed against moisture, and the light reflects making it brighter inside.
Check the mistint pile, Freecycle, Restore, etc. to get high-quality paint on a budget. You don't want to invest a lot of time in painting only to have the paint not last.