2015 update: the flexbox approach

There are two other answers briefly mentioning flexbox; however, that was more than two years ago, and they don't provide any examples. The specification for flexbox has definitely settled now.

Note: Though CSS Flexible Boxes Layout specification is at the Candidate Recommendation stage, not all browsers have implemented it. WebKit implementation must be prefixed with -webkit-; Internet Explorer implements an old version of the spec, prefixed with -ms-; Opera 12.10 implements the latest version of the spec, unprefixed. See the compatibility table on each property for an up-to-date compatibility status.

(taken from https://developer.mozilla.org/en-US/docs/Web/Guide/CSS/Flexible_boxes)

All major browsers and IE11+ support Flexbox. For IE 10 or older, you can use the FlexieJS shim.

To check current support you can also see here: http://caniuse.com/#feat=flexbox

Working example

With flexbox you can easily switch between any of your rows or columns either having fixed dimensions, content-sized dimensions or remaining-space dimensions. In my example I have set the header to snap to its content (as per the OPs question), I've added a footer to show how to add a fixed-height region and then set the content area to fill up the remaining space.

html,
body {
  height: 100%;
  margin: 0;
}

.box {
  display: flex;
  flex-flow: column;
  height: 100%;
}

.box .row {
  border: 1px dotted grey;
}

.box .row.header {
  flex: 0 1 auto;
  /* The above is shorthand for:
  flex-grow: 0,
  flex-shrink: 1,
  flex-basis: auto
  */
}

.box .row.content {
  flex: 1 1 auto;
}

.box .row.footer {
  flex: 0 1 40px;
}

<!-- Obviously, you could use HTML5 tags like `header`, `footer` and `section` -->

<div class="box">
  <div class="row header">
    <p><b>header</b>
      <br />
      <br />(sized to content)</p>
  </div>
  <div class="row content">
    <p>
      <b>content</b>
      (fills remaining space)
    </p>
  </div>
  <div class="row footer">
    <p><b>footer</b> (fixed height)</p>
  </div>
</div>

In the CSS above, the flex property shorthands the flex-grow, flex-shrink, and flex-basis properties to establish the flexibility of the flex items. Mozilla has a good introduction to the flexible boxes model.

Warning! This answer is too old and doesn't work on modern browsers.

_{I'm not the poster of this answer, but at the time of writing this, this is the most voted answer by far in both positive and negative votes (+1035 -17), and it's still marked as accepted answer (probably because the original poster of the question is the one who wrote this answer).}

As already noted many times in the comments, this answer does not work on most browsers anymore (and seems to be failing to do that since 2013).

After over an hour of tweaking, testing, and trying different styles of markup, I think I may have a decent solution. The requirements for this particular project were:

1. Inputs must be on their own line.
2. Checkbox inputs need to align vertically with the label text similarly (if not identically) across all browsers.
3. If the label text wraps, it needs to be indented (so no wrapping down underneath the checkbox).

Before I get into any explanation, I'll just give you the code:

label {
  display: block;
  padding-left: 15px;
  text-indent: -15px;
}
input {
  width: 13px;
  height: 13px;
  padding: 0;
  margin:0;
  vertical-align: bottom;
  position: relative;
  top: -1px;
  *overflow: hidden;
}

<form>
  <div>
    <label><input type="checkbox" /> Label text</label>
  </div>
</form>

Here is the working example in JSFiddle.

This code assumes that you're using a reset like Eric Meyer's that doesn't override form input margins and padding (hence putting margin and padding resets in the input CSS). Obviously in a live environment you'll probably be nesting/overriding stuff to support other input elements, but I wanted to keep things simple.

Things to note:

• The *overflow declaration is an inline IE hack (the star-property hack). Both IE 6 and 7 will notice it, but Safari and Firefox will properly ignore it. I think it might be valid CSS, but you're still better off with conditional comments; just used it for simplicity.
• As best I can tell, the only vertical-align statement that was consistent across browsers was vertical-align: bottom. Setting this and then relatively positioning upwards behaved almost identically in Safari, Firefox and IE with only a pixel or two of discrepancy.
• The major problem in working with alignment is that IE sticks a bunch of mysterious space around input elements. It isn't padding or margin, and it's damned persistent. Setting a width and height on the checkbox and then overflow: hidden for some reason cuts off the extra space and allows IE's positioning to act very similarly to Safari and Firefox.
• Depending on your text sizing, you'll no doubt need to adjust the relative positioning, width, height, and so forth to get things looking right.

Hope this helps someone else! I haven't tried this specific technique on any projects other than the one I was working on this morning, so definitely pipe up if you find something that works more consistently.

Warning! This answer is too old and doesn't work on modern browsers.