Estoy en Ubuntu 15.04 y recibí el mismo error que se indicó anteriormente.
lo hice :
sudo apt-get install libmysqlclient-dev
Después de esto hice:
gem install mysql2
Y ahora puedo hacer con éxito
rails new <app_name> -d mysql
sin errores.