There's also mod_deflate your apache person can try.

If you want to see the header, use something like snoop or tcpdump or Firefox's Live HTTP Headers extension on a site that uses compressed pages. Here's one. Then you have to write the header soon enough in your CGI; and then compress everything following (once again, with the IO layer it'd be easier, as well as better since you don't have to wait until you have all the data before sending it).