If you're not sure if you have the SDKs, can you confirm you have the files under /Developer? Check for /Developer/SDKs/MacOSX10.4u.sdk/usr/X11R6/include/X11
I don't remember having to do anything special to get gcc to find these files.
From what I've noted, the usual trigger seems to be that the X11SDK.pkg package wasn't installed.
Typical PATH export is:
export PATH="/bin:/sbin:/usr/bin:/usr/sbin"
If you're working with Fink, there's a call to the following needed:
. /sw/bin/init.sh
See
http://finkproject.org/doc/users-guide/install.php
But I'd first make sure the X11 SDK was installed. I'd guess that is missing.