It should be said that currently, once MySQL has been upgraded beyond what ships with the operating system, you will not be able to upgrade Plesk.  This is due to the way that the upgrade scripts themselves run.  They will always look for the “stock” version of MySQL, and do not know how to handle a different version.

Having said that, it is relatively simple to upgrade.  You should first make a COMPLETE backup of all of your MySQL databases.  There are many ways to do this, so it will not be covered in this article.  After your backup is completed, all you really have to do is download the RPMs for the version you wish to upgrade to.  For the purpose of this article, we will assume that you wish to upgrade to 4.0.27.  You would need to get the following RPMs:

MySQL-server-4.0.27-0.i386.rpm
MySQL-client-4.0.27-0.i386.rpm
MySQL-devel-4.0.27-0.i386.rpm
MySQL-shared-compat-4.0.27-0.i386.rpm

After downloading these, all you have to do to upgrade, is issue the following command in the directory that you downloaded the files to:

rpm -Uvh MySQL-*

This will upgrade all of your current installation to 4.0.27.  It should be noted, that because you are using the -U option, it is possible for the old rpm to remove the mysql user.  If that happens, you will need to add it back into your passwd and shadow files.