If Apache is set up correctly (assuming it's a current install and you selected the defaults, it is), the problem may be that you are
ing something before you print the header. I was recently bit by this bug when I forgot to remove a debug print statement from a script.
You can test whether this is the case by running the cgi script from the command line and ensuring that the first output from the script is/isn't the text/html header.