It's all about the lighting!
Most people seem to think it's all done in 'shop but a lot of work goes into the actual setup. Many of the supposed "Dave Hill look" imitations have just used HDR style tonemapping, and the results are nothing like the work of Dave Hill. Compare this:
http://www.flickr.com/search/?q=dave%20hill%20look&w=all
with this:
http://www.davehillphoto.com/
No similarity at all! Yes there is a lot of post production in Dave's work, but you need to get close with the lighting in order to get the same look. Here is an example, showing what is possible with lighting alone. The first image is straight out of camera:


...the second image is the final image after Photoshop, mostly saturation, contrast and a little high pass filter in an overlay blending layer. I should have pointed out I didn't set out to get the Dave Hill look, I just wanted to play around and see what worked with the subject (the singer in a Ska band). I could have done more in post to get slightly closer to Dave's images.
The key to the look is sculpted light. This means directing large lightsources at oblique angles to the subject. I used two square softboxes right up close and a bare hotshoe strobe for the hair light. Here's how the lights were placed:

The softboxes were brought in really close to maximise the softness of the light, and angled toward the camera to increase the sculpting effect and falloff nicely across the face. Two "gobos" were used to stop flare interfering with the picture (the black lines in the diagram). This is absolutely essential when angling the strobes toward the camera! The hairlight at the back was bare (i.e. no modifier) to really penetrate Aaron's hair and make it glow. As less power is required for an unmodified light, I substituted a hotshoe flash for the big monolight.
You can replicate this look on the cheap with a couple of hotshoe flashes but softboxes are important. Something like an umbrellabox is a good option if you're using small battery flashes. You just don't get the same effect with umbrellas as they spill too much light out the sides, and are in general harder to fine tune as you don't get a crisp edge to the light. The curved profile of the umbrella also makes it hard to get close. Getting close basically makes your softboxes bigger. Dave would have used huge octoboxes further away to give the model more space but he gets paid more than I do ;)
You can actually see Dave's setups in his behind the scenes videos (which I've just noticed you mentioned in your question!). And yup there are some big octoboxes! http://www.davehillphoto.com/bts/
Here's another example of the same look in a group shot I did for the band Asking Alexandria. This one required a bit more post production (as lighting groups is much harder) so I'll take it step by step to show you what sort of post production you can do to push the look to its limits.

As before, lighting is still very important. I used a very similar setup to the previous example but with the softboxes much more symmetrical. The models stood in a triangle pattern so the light hit everybody. The hairlight is also much higher this time as we're lighting the top of the head, not shining through anyone's hair (which would have required three hairlights in this example). You can see the lightstand for the hair light in the straight out of camera shot, behind the guy on the left.

Here's the image after Raw conversion in Adobe Camera Raw, where I added a little of the clarity slider, brought up the black point and used a lot of the fill light slider. I wasn't going for any specific look, just to get an image with detail and a good tonal range to work with. The background clutter has been removed by a manual selection. Also note I've made the image taller by adding more black. I planned to do this so I shot the original very tightly cropped to make the most of my megapixels (I didn't do this with Aaron as some of the shots we took involved a lot of movement).

Here I've faded a little of the ground into the image with a gradient mask in order to ground the models and make them look a little less like they're floating in space!

Next I went mental with the Photomatix tonemapping plug-in! With any sort of HDR work, taste and subtlety is important. I find the easiest way to achieve this is to push it as far as I can and then fade it into the original at a very low opacity to retain some realism.

Here, it is reduced in opacity to 30%. I actually lowered it to 15% in the final version, as I just wanted to show the effect in bringing out the details in the legs and shoes that was lost due to the fact I concentrated on lighting the faces (and didn't have any striplights to hand). It's also done a nice job with the hair.

Now here's pièce de résistance of the post processing. I've duplicated the original applied a high pass filter (which removes small details such as noise) and leaves large scale tone changes. The layer is blended back in at 30% with the blending mode set to overlay. This is very important, as it sort of amplifies the high pass by lightening the lights and darkening the darks. It's starting to look how I want it now.

Here's the final image after some fiddling; dodging and burning here and there, and some minor colour correction (I moved the jeans away from cyan and desaturated for a more pleasing look). Desaturated skin tones makes this lighting technique look better in almost all cases. Finally, the image is resized and sharpening applied, leaving an image which I think captures the look you are going for based on the examples posted.
It's worth noting that you need a dark place in order to pull this off otherwise you lose control over the light and you will have difficulties getting the deep shadows required for maximum contrast. The first image of Aaron was shot in a black walled studio, but if you don't have access to a studio you can get the same effect in any large space. The size is important as the light that gets reflected back from other objects falls off with the squre of the distance (double the space, 4x less light bouncing off walls), up to the point where it is totally overpowered by the subject and you get a nice black background. If you're looking for a large space, the great outdoors comes in very handy!