I am assuming that you are talking about the difference in highlights and shadows between those two pictures (the first had very blown out sky), and not the somewhat "gritty" effect of the latter. Aside from the obvious in-camera correction of reducing exposure (as the first image was certainly overexposed), which I believe would have had a very similar effect, there are multi-exposure blending techniques that can solve problems with scenes with high contrast.
There are two primary ways where such images with broad apparent dynamic range can be created. The most common way is HDR, or High Dynamic Range, processing. HDR processing usually involves two or more exposures of a scene, but ranging up to perhaps a dozen, that are blended to create a single high dynamic range image that stores color information using floating point numbers, rather than integers. The dynamic range of a normal image is quite limited, however the dynamic range of an HDR image can be nearly infinite, and as it is "dynamic", can be adapted to properly render just about any image.
Classically, HDR images are created by using the AEB feature, or Auto-Exposure Bracketing, of your camera to take several exposures of a scene. One at the exposure setting you (or the camera) chooses, one under exposed and one over exposed by the amount of stops specified in the AEB setting. These three images are then merged using a tool like Adobe Photoshop's "Merge to HDR" feature, or Photomatix (a program dedicated to HDR processing.) The resulting 32-bit floating point HDR image can be converted to 16-bit or 8-bit, and "tone mapped" to compress the very broad dynamic range of the HDR image (which is actually well beyond what any computer screen or printer is remotely possible of displaying) into the limited dynamic range of a normal image. This process is pretty manual, and can require quite a bit of fine tuning to generate a proper LDR (low dynamic range) image that "appears" to have a higher range of contrast than it actually does.
A newer alternative to HDR is Exposure Fusion, or Enfusion. This technique is similar to HDR in that it takes multiple exposures and merges them. Unlike HDR, however, Enfusion is a far simpler process that uses a much more advanced algorithm to directly create an LDR image that looks "correct" without all the manual fiddling that is usually necessary with HDR. There are some options that can be used to tweak an enfused image, however most of the time they are not necessary, and when they are, the amount of fiddling is usually pretty minimal. There are two tools available today that can create enfused images...the original, free Enfuse tool, and Photomatix Pro, which also does HDR, but costs some dough. Enfuse is a command line tool, and if it produces an enfused image that you don't think looks quite right, it can be complex to figure out the right command line options to tweak. Photomatix, on the other hand, is all visual, and it is a lot easier to tweak when necessary.
If your question was about how to get the particular "tone" and "atmosphere" of the second image, and not about how to improve dynamic range, then that is a whole different story. I think that particular "look" is referred to as the "gritty" look, and there are countless tutorials and articles on the net that cover that, so I won't do into detail here. (Not to mention that I don't process my images that way anyway, and I'm not the right person to offer you any tips. ;))