Installing rmagick on OS X can be a major pain if you installed ImageMagick with fink. The solution is relatively simple, but I found a lot of different 'solutions' via google, none of which worked for me (including installing from source!), so take it with a grain of salt. You need to install the imagemagick-dev package; specifically, imagemagick10-dev, since imagemagick1-dev is compiled with HDRI support, which is incompatible with rmagick.

Similarly, on Ubuntu, you need the dev packages installed - both for Ruby and for ImageMagick. Off the top of my head, I believe these are ruby1.8-dev and libmagick9-dev, at the time of this post. Presumably this or something similar would work on Debian as well.