結論
libmysqlclient-dev を入れましょう。
# apt-get install -y libmysqlclient-dev
# gem install mysql2 Building native extensions. This could take a while... Successfully installed mysql2-0.4.5 Parsing documentation for mysql2-0.4.5 Installing ri documentation for mysql2-0.4.5 Done installing documentation for mysql2 after 1 seconds 1 gem installed