This really depends on the Linux distro you are using. Most binary distros ship the headers separate from the application itself, often in a -devel package.
For instance, on my Fedora 12 machine the
mysql-devel package has the following description:
MySQL is a multi-user, multi-threaded SQL database server. This package contains the libraries and header files that are needed for developing MySQL client applications.
On Fedora, CentOS, or RHEL,you can install this package by
yum install mysql-devel as root. Debian and Ubuntu systems will have a similar package name and command for apt.