Answer was similar to the one Wrikken posted — here’s what I did to fix it for the sake of future readers.
(This is for RHEL 5.5 — similar but different commands apply for Ubuntu/Debian/etc.)
Doing sudo yum list installed will print out all installed packages on your machine (note: yum on RHEL requires you add a Red Hat Network repository [I use EPEL], and run it via sudo).
I had mysql and mysql-server, which explained why MySQL worked fine for every pre-existing app, but no mysql-devel, which is necessary to fix that mysql.h is missing error and similar other build errors.
Long story short, after a mysqldump -u root -ppassword --all-databases > full-dump.sql for safety, it was fixed with a simple
sudo yum install mysql-devel