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.