normalmente i file include si trovano in /usr/include, verifica che sia così e che stdio.h sia elencato.
Come hai installato gcc?
Mandaci solo il file prova.c.
ciao
sergio