Create your gradation in an alpha channel. Add 2 pixel noise. Apply a curve to the channel pushing your lower left point to the right 2 and your upper right point to the left 2 (input 2 and 98 respecively) Make the channel into a selection. Create a new layer and fill selection with the color you want. No banding what so ever.
This is also the best way to create shadows that won't band. I start by creating my shadow in layers using only black. When it is how I like it I turn off all layers except my shadow layers. Duplicate my black channel and follow instructions above.
To check for banding you can add a solar curve as Chris pointed out. See attached PSD file. Turn on the solar curve to reveal banding. I did a simple gradation and a drop shadow for reference. If you want to change the color of the gradation or shadow, simply pixel lock the layer and fill with new color or paint in where desired.
If it downloads as "Gradations.psd.txt" just delete the ".txt" file extension and open with PS.