Click derecho en el escritorio -> Crear nuevo -> Archivo -> Enlace a aplicación
En la pestaña "General" eliges el nombre y el ícono. Después en la pestaña "Aplicación", en "Comando" escribes el comando a ejecutar. Debe ser algo así como:
/usr/bin/mysqlcc
O algo parecido (el comando exacto dependerá de la manera en que instalaste el mysql, pero como no nos has dicho cómo lo hiciste, no puedo saberlo). Luego le das "Aceptar" y listo.
Fácil, ¿no?
