aqui te dejo la ayuda oficial de mysql para la instalacion de mysql en linux, ahora debes saber si quieres instalar el servidor y el cliente en la maquina o solo el cliente para que te conectes a otra maquina que tiene instalado el mysql server, ahora revisa los downloads y baja lo que necesitas de acuerdo a tu distribucion de linux
de donde bajar los rpms:
mysql 4.1
http://dev.mysql.com/downloads/mysql/4.1.html
mysql 5.0
http://dev.mysql.com/downloads/mysql/5.0.html
ayuda para la instalacion:
http://dev.mysql.com/doc/refman/5.0/en/linux-rpm.html