installation mysqldump
Solution 1:
How about ... doing what was printed on the terminal?
% sudo apt-get install mysql-client-5.1
or
% sudo apt-get install mysql-client-5.0
(pick the right version based on whats installed on your machine)
Solution 2:
For CentOS, RedHat and Fedora install:
sudo yum install mysql