This problem can be one of a few things:
- Posterization caused by JPEG image compression when over-compressing a JPEG.
- Posterization caused by low color information in lower signal areas.
- Quantization caused by high bit depth, wide gamut image information being displayed on a low bit depth computer screen.
First, for case #1, the solution is really to use less compression. Smooth gradients do not compress well, as compression really ends up doing the same thing that causes cases #2 and #3: bucket rich color information into anemic color information.
Regarding case #2. At the low end of the image signal range (the shadows and lower mid-tones), sometimes colors in a gradient organize into large bands of the same color separated by discrete steps. It may only be a difference of a one or a very few levels between one band in a shadow gradient and another, but that difference can often be detected by our eyes (which are very sensitive to changes in luminance, especially when the bulk of that luminance is similar in tone.) Sometimes minor discrete changes in luminance are rendered incorrectly due to a lack of precision in rendering algorithms or a lack of bit depth (which is actually really case #3...but we'll get to that). At the high end of the signal range, there tend to be many more levels available, and gradations can be much smoother using more changes in tonality, so banding does not show up as well in brighter photos or brighter areas of a photo than it does in middle toned and shadow areas.
Leading on from case #2 is case #3: bit depth. Most digital photographs these days are capable of representing a far, far richer set of data, both in terms of luminance and gamut, than the average computer screen is capable of. Most cameras are 12 to 14 bit, thus producing two to four orders of magnitude more color information than the average 8 bit computer screen is capable of. This causes quantization of color information when it is transformed from its original color space (that of the camera device, 14-bit RAW image and ProPhotoRGB gamut most often) into the computer screen color space, usually 8-bit sRGB gamut. That transformation has to group the greater volume of colors into a lesser volume of colors, and at a lower precision to boot. The result is often posterization and what some would call "noise" or "grain" in gradients.
There is nothing actually wrong with your image, it is still there, in tact, in all of its original high-precision, high bit depth, wide gamut beauty. Your hardware is simply incapable of handling it in it's native form. Modern software and hardware is usually capable of dithering during this transformation from "high" to "low". That is the source of the "grain" that many can see, however that graniness is actually the reason the posterization does not look a lot worse when viewing a 14-bit image on an 8-bit screen.
The solution to case #3, and to a degree case #2, is to upgrade to better hardware. Better hardware could be a better video card that is capable of crunching more complex pixel shaders. Increasingly these days, image editors like Photoshop are moving to GPU-based rendering. The average consumer-grade gaming GPU is geared for speed, and to achieve that speed, precision is often sacrificed. Switching to a professional-grade GPU, like Nvidia Quadro, will usually allow more precise rendering of the kind of shaders used in a tool like Photoshop (and, hopefully, Lightroom 5 when it finally hits.) That should help alleviate some of case #2, where it is caused by lower precision rendering algorithms.
Moving to a professional-grade video card like a Quadro will also open up another avenue: 10-bit displays and high bit depth hardware LUTs (color Look Up Tables.) Screens from the likes of Eizo, NEC, LaCie, etc. are usually capable of 10-bit rendering from a 12, 14, or 16 bit hardware LUT. The high bit depth LUTs allow for billions of colors, and the 10-bit displays are able to render those billions of colors using advanced hardware dithering (this actually achieving real-time display of all 12 to 16 bits of color information by interleaving the extra color information over time via the 60hz refresh rate). Using a 10-bit display with a 14 or 16 bit LUT will effectively eliminate any posterization when editing 14-bit RAW files. The catch here, though, is that you must use software that is actually capable of taking advantage of 10-bit displays, their LUTs, and the GPU's that drive them. Some Adobe software like Photoshop CS6 supports this, but only when you have a professional-grade OpenGL GPU like Quadro, a DisplayPort (neither DVI in any form nor HDMI will work) connected to a legitimate 10-bit display.