The MySQL cache plugin is a way to store session data on disk so that it survives a restart of the SharService. It is not suitable for load-balanced server farms and is not a shared multi-process cache. MySQL in general is a bad database for applications that do a lot of writes, and we suggest alternate plugins with more reliable databases for such applications.
The plugin requires the Embedded MySQL library (libmysqld) from version 4.0 or higher. It doesn't get built by default and won't be found on most systems. Building it from source requires that you enable threads, shared library support, PIC options, and various things that may or may not work with their makefiles out of the tarball.
The Shibboleth configure script will look for the embedded library, and if it can't find or link with it, the plugin is skipped.
An example command that worked on Solaris 2.8 with MySQL 4.0.13 is:
./configure --prefix=/opt/mysql \
Apparently, libz may now be required on some platforms, particularly Linux. Investigation is ongoing, but see https://mail.internet2.edu/wws/arc/shibboleth-users/2005-03/msg00033.html