So your gcc should be finding /usr/include/stdio.h if you have it. Is it there? As far as I can tell from the package file lists, it's supposed to be part of the cygwin base system (i.e. even if you haven't installed the compiler it should be there).

Are you missing any other header files? <stdlib.h> and <string.h> are good test candidates.

Here are some commands to investigate the cygwin package and whether it contains the file:

cygcheck -f /usr/include/stdio.h
cygcheck -c cygwin
cygcheck -l cygwin | grep stdio
UPDATE: so it seems I'm behind the times and there's a cygwin-devel package now. The header files aren't in the base cygwin package any more. To check the correct package on the latest cygwin, you'd use

cygcheck -c cygwin-devel
as has already been done in the comments. And since it's listed as "incomplete" the solution is probably to reinstall it using cygwin's setup program.