I just redid my site (listed below) using fluid design, all divs and css, very minimal tables.
Even if you do most of your work in tables you can still make the header fluid very easily. But the trick is that you need a header that has
at least one edge that has a repeatable pattern or a solid color.
If you look at my header - mouse over the water and do a right mouse click and then "view background image" in firefox, or "save background" if you use IE (you will need to view the image from wherever you save the file).
The image has water flush up to the right edge. This edge is very hard to stretch or make fluid. However, the left edge is a repeatable pattern. So, I edit the header in something like photoshop. I then use the crop tool and crop off just the left edge for about 15-20 pixels wide, full height. Save this little slice to a new file called hdr-bg.jpg.
Now, what I would do is use the hdr-bg.jpg as the background for the table. I would then setup the background to repeat-x. This covers the table cell for as wide as the cell goes.
Now, since my image has a unique right side and the background only matches the left side, I am going to put the image in the cell but right align the image. This pins it to the right, and make the left side fluid.
What if your image is the same on both sides, or has the same color on both sides? You can set the background color of the cell to match the background of the image. Then just center the image.
The same concepts work for your content and menu columns.
But I suggest you start with the header and understand the concepts, then you can work on the content part of your pages.
If folks are interested, I might have a link to a website that explains this with pictures, that I can't really do well here.
Good Luck.