Puedes hacer algo tan simple como:
Código PHP:
<?php
system("nombre_ejecutable_C param1,param2,...,paramn ");
?>
Por otro lado, un CGI es un programa cualquiera ejecutable, que escribe ciertas cabeceras html para que las interpreten los navegadores y así mostrar contenido. En Apache se colocan esos programas generalmente escritos en C, Perl o Python en un directorio especial y con eso basta.