Here's what I've done so far:

sudo apt-get install imagemagick libmagickcore-dev

This did not throw any errors, so I think that ImageMagick is installed fine. Then I tried installing the gem:

sudo gem install rmagick

This resulted in the following error:

ERROR:  Error installing rmagick:
    ERROR: Failed to build gem native extension.

/usr/bin/ruby1.8 extconf.rb
checking for Ruby version >= 1.8.5... yes
checking for gcc... yes
checking for Magick-config... yes
checking for ImageMagick version >= 6.4.9... yes
checking for HDRI disabled version of ImageMagick... yes
checking for stdint.h... yes
checking for sys/types.h... yes
checking for wand/MagickWand.h... no

Can't install RMagick 2.13.1. Can't find MagickWand.h.
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of
necessary libraries and/or headers.  Check the mkmf.log file for more
details.  You may need configuration options.

Provided configuration options:
    --with-opt-dir
    --without-opt-dir
    --with-opt-include
    --without-opt-include=${opt-dir}/include
    --with-opt-lib
    --without-opt-lib=${opt-dir}/lib
    --with-make-prog
    --without-make-prog
    --srcdir=.
    --curdir
    --ruby=/usr/bin/ruby1.8


Gem files will remain installed in /usr/lib/ruby/gems/1.8/gems/rmagick-2.13.1 for inspection.
Results logged to /usr/lib/ruby/gems/1.8/gems/rmagick-2.13.1/ext/RMagick/gem_make.out

What do I need to do to install rmagick on Ubuntu 10.04?