You need to use the -palmos3.5 switch to your command line. That makes
gcc add all of the extra includes that are appropriate to the 3.5 sdk.
In addition, I would recommend that you use the 4.0 sdk (in which case
you would use -palmos4.0). You can still target 3.5 (or even 2.0)
devices with the 4.0 sdk, and this is the "official" sdk that developers
should be using. It will save you huge pain later if you start using the
latest SDK today.
Finally, it appears that the prc-tools in debian/unstable is still only
0.5. This is woefully out of date, and probably won't support the 4.0
SDK correctly (the -palmos switch's implementation has changed). The
latest tools at prc-tools.sourceforge.net are 2.1. If you plan to do any
serious development for PalmOS, you need that version, or better yet the
version from CVS. Plus, if you are going to do big projects that need
multisegmenting, then there is an extra patch that lets gdb correctly
work with multisegmented apps. I'm not sure if that patch has made it
into cvs or not.
I have some prc-tools .debs that are not debian-policy compliant; I can
make them available on a by-request basis if anybody is interested.