A mi por lo menos siempre me da problemas esto cuando pongo una aplicación y producción en un servidor nuevo y he de tirar de la chuleta, en Google aparecen otras formas, pero esta me parece la más sencilla y nunca me ha dado problemas a diferencia de otras (como instalar desde el código fuente).

$ apt-get install imagemagick libmagick9-dev
$ gem install rmagick

Con esto ya podrás usar RMagick directamente o gemas como https://github.com/thoughtbot/paperclip en Ubuntu.