http://hoohoo.ncsa.uiuc.edu/cgi/intro.html
basically all data that the scripts process (like this message) must be passed to the script somehow, the interface that allows this is refered to as CGI, so yes, all your php scripts use the CGI.
the reason some webhosts may not like PERL scripts (.cgi) is because they create a new process each time they are run, whereas asp, (and i guess php) doesn't, so its less strain on the server