Here is the fix that worked for me when I received the error:
"Your PHP installation appears to be missing the MySQL which is required for WordPress."
For background, I am running:
Windows 2000
Apache 1.3.29
PHP 5.04
MySQL 4.1
The problem seems to have been that although I changed the PATH environment variable to include my PHP install directory (c:\php5.04) it was not finding my php.ini file there. This is odd because I renamed all other php.ini files on the system, so I don't know what it was using... maybe it doesn't need a php.ini file at all and if it can't find one it loads defaults. In any case, I could tell it wasn't loading it because when I viewed a php_info page it wasn't giving me updated values for the extension_dir and various other settings. So I tried copying my php.ini file into the winnt directory, and that got it reading the file.
However, then I was getting errors that 2 mysql dlls could not be loaded. I found a post on another site that recommended renaming versions of this file other than the one in the php install directory. I did that and it worked.
I hope that helps... I hope wordpress is worth it!