Généralement, stdio.h se trouve dans le répertoire /usr/include (c'est d'ailleurs dans cet endroit que tu as la plupart des includes de bibliothèques).
Cet include est livré avec un package de ta distribution de linux (debian, mandriva, ubuntu ,etc...). Tu peux le trouver dans le package libc6-dev. Vérifie qu'il est bien installé (apt-get install libc6-dev sur ubuntu/debian, urpmi libc6-dev pour mandriva, je ne connais pas les autres). Par contre effectivement, c'est étonnant qu'il ne soit pas présent alors que ton compilateur l'est, d'autant plus que les distributions récentes gèrent les dépendances de packages et que gcc doit certainement être dépendant de "stdio".