Open a terminal window, and use the following command:
sudo apt-get install mysql-server-4.1
If you are running PHP you will also need to install the php module for mysql 4:
sudo apt-get install php4-mysql
To create a new database, use the mysqladmin command:
mysqladmin create
