Worked for me with Nokogiri 1.4.4 on Ubuntu 10.04 LTS:
# ruby developer packages sudo apt-get install ruby1.8-dev ruby1.8 ri1.8 rdoc1.8 irb1.8 sudo apt-get install libreadline-ruby1.8 libruby1.8 libopenssl-ruby # nokogiri requirements sudo apt-get install libxslt-dev libxml2-dev sudo gem install nokogiri