One thing I learned yesterday is that, if you have large chunks of solid color, a .gif is good. for photos, .jpg works better most times.
My header was one big graphic with Photoshopped text and tabs on the left, and a big picture on the right. 31kb .gif. When split in 2, left side .gif and right side .jpg, the whole thing dropped to 13kb. It was amazing. Lesson learned.
A bunch of our member took two different HUGE starting files, and everyone used their favorite image compression technique to shrink and squash them as much as possible... and the best part is that eveyrone told how they did it! Some great tips to be had in those threads.
Also, there was a more recent discussion of people's various favorite compression programs here [webmasterworld.com].