It would make things easier in the long run, how big is the site? I highly recommend you do it, but you don't have too.
If you sticking with the tables, the first thing I would do is make them all the same width, so they don't look out of line.
Next I would give the side bar table the same background color as everything else so you don't have that blue box down the bottom.
Then I would remove the border from the logo, and give that table a background image to make the whole think look like one big image, I have attached what I would use.
That would at least tidy things up a bit, then you could add some background images to the menu and sidebar but I leave that till later.
By the way I notice you have
border-right : 1px solid #FFFFFF;
border-left : 1px solid #FFFFFF;
border-top : 1px solid #FFFFFF;
border-bottom : 1px solid #FFFFFF;
in your css file, do you know that could be written as
border: 1px solid #fff;