How to smooth shade an object while retaining hard edges?
There are a few ways to do this but the quickest and most efficient (in your case here) is to just smooth it the same way, using Shade Smooth and then adding an Edge Split modifier to the mesh.

From the wiki


  The EdgeSplit modifier splits edges within a mesh. The edges to split
  can be determined from the edge angle (i.e. angle between faces
  forming this edge), and/or edges marked as sharp.
  
  Splitting an edge affects vertex normal generation at that edge,
  making the edge appear sharp. Hence, this modifier can be used to
  achieve the same effect as the Autosmooth button, making edges appear
  sharp when their angle is above a certain threshold. It can also be
  used for manual control of the smoothing process, where the user
  defines which edges should appear smooth or sharp


Here it is as you have it above..



With the modifier added



Additionally, you can see some more tips here for getting good quality on hard surface models. BlenderCookie has a tutorial (archived) on getting nice sharp edges.