Here's an oldy but good discussion about the use of headings that I thought was kind of fun, as it got beyond the mechanical issues into what was behind them...
New Paragraph after new Heading?
My feeling is that you need some paragraph content following after each heading and relating to it. Otherwise, the heading isn't "heading" anything.
Incidentally, some CMSs, or designers on their own, have really weird ideas, IMO, about what deserves h1, h2, etc. I've had screaming battles with designers who insisted that the first text on the page, whatever it is, should be an h1, which is total nonsense.
Some CMS systems automatically make the site name an H1, a setup that makes a meaningful heading hierarchy hard to create. Chances are that headings have been so misused that they're generally ignored.
We are moving into a time of proper markup getting increase respect once again, so possibly a page that uses headings well will gain from that. Properly used headings are a good way to organize a page in any event, and I like using them.
Regarding size, I think some of the prescriptions I'm seeing above are really overly picky. I don't think heading size after CSS was regarded that specifically by the engines, though browsers may render text in the sizes mentioned.
Lucy's description of headings without CSS is a helpful way to regard the basic point of it all, though... that before CSS, you could consider html visual presentation to be a metaphor for heading number, order, and importance.
CSS did free up headings from the ugly old giant H1 font formatting (remember those pages in Times New Roman?). I've always felt that a heading should visually look like a heading... ie, be bold or distinctive in some way, perhaps at least a degree larger than paragraph text... but how much was up to the designer, and the exact size didn't matter that much.