I've written a HOWTO and a FAQ about running CGI programs. They can be found here:
HOWTO:
http://www.hiawatha-webserver.org/howto#3.3FAQ:
http://www.hiawatha-webserver.org/faq (CGI section)
If that doesn't help you, please let me know.
P.S.
Make sure you use the php binary in the sapi/cgi directory, NOT the one in sapi/cli.
update:
links to HOWTO and FAQ point to this website instead of old Hiawatha website