Instale los paquetes imagemagick y libmagickwand-dev (o libmagick9-dev ). Entonces deberías poder instalar Rmagick Gem.
sudo apt-get install imagemagick libmagickwand-dev
Si no, te faltan paquetes de desarrollo relacionados con Ruby como build-essential y ruby1.8-dev . Si ese es el caso, una consulta genérica "ubuntu install ruby 1.8" en Google debería resolverlo.
No necesita mucha de la otra basura en estas respuestas, solo:
sudo apt-get install libmagickwand-dev