To clarify, here is what you are apparently talking about:

This is a 1:1 crop from the middle of the picture.

There is no grain here. What I see looks like sensor noise. "Grain" makes no sense for such a digital picture anyway. Note that the clouds in the background look fine, but there is significant noise in the much darker foreground areas.

Basically, this scene has too much dynamic range for your sensor. To fix this, either take multiple images at a sequence of f-stops and stitch them together with a technique called HDR (high dynamic range), or get a better sensor. This is one area where sensor quality really matters. It would help to know what camera this was taken with. If this was a cheap point and shoot, then a better camera would probably make a significant difference. If this was a Nikon D3s, then your only option is multiple exposure HDR. (However, having experience with a D3s, I think it could do this natively with significantly less noise that exhibited here.)

Of course this is all assuming you exposed optimally for the sensor you do have. That means the brightest areas (the whitest parts of the clouds) need to be almost at the brightest raw values. Using the 0-1 scale for raw values, if the brightest areas were .9 or so, then you've done what you can. On the other hand, if they were .5, then you wasted a whole f-stop of precious sensor dynamic range. 0.25 would be 2 f-stops, etc.

You say you underexposed, but relative to what exactly? Some cameras have a mode that does exactly what you want in this case, which is to expose the highlights to hit just under the top of the sensor range. If that's what your camera was already doing, then underexposing only wasted dynamic range.

Again, it would be good to know the camera and what the histogram of the raw data actually was.