Shared hosting?

First of all, the message only appears if the MySQL is under heavy load and unable to reply to other requests. Most commonly this occurs on shared hosting environments that are simply not fit for Magento: Magento makes intensive use of the database, and if one single physical server is used for 100s of Magento instances, things are bound to go wrong.

If this error MySQL server has gone away appears, the first thing to do is to contact the system administrator of the hosting environment, to ask him/her to deal with it. The rest of this tutorial assumes you have root-access to solve the resource problem yourself.

MySQL configuration

Because Magento makes such intensive use of the MySQL database, assigning system resources is dangerous at times. If MySQL is configured to use an innodb_buffer_pool_size of 2Gb while there is only 2Gb of RAM in the server, performance problems will occur without doubt. All tutorials regarding MySQL optimization come into the picture here.

The reason why the entire MySQL server might become unavailable, might be due to memory shortage but also the availability of network connections might cause issues. For instance, make sure the wait_timeout is not shorted than 10 seconds. A value of 60 is good enough. Also set the option reconnect to 1, which makes sure that MySQL tries to reconnect after a connection failed:

[mysqld]
wait_timeout = 60
reconnect = 1

PHP directives

Within the PHP configuration the following values might also be considered:

mysql.connect_timeout = 60
mysql.allow_persistent = On

Server optimization

Far more important, is the comment earlier made about shared hosting servers, and the way the hardward is tuned for the software being ran (Magento in this case). Memory-optimization is vital for this. 

Sometimes DNS lookups might cause timeouts as well. If the MySQL server is running on the same server as the Apache server, it's wise to use 127.0.0.1 or localhost as database-host in your database configuration. Another trick is to add the relevent database-host to the /etc/hosts file.

If you want us to help out here, we are happy to assist. Yireo has years of experience optimizing its own hosting environment (some of us used to be a Magento hosting provider in a far past) as well as speeding up environments of customers. With our various services, we give you the expert help you need.