To diagnose and solve, here's what worked for me.

To find out what failed, go to your ruby gems directory.

For example:

$ cd <MY RUBY DIRECTORY>/lib/ruby/gems/2.0.0/gems

If you don't know your gem directory, try this:

$ echo $GEM_HOME/opt/gems/2.0.0$ cd /opt/gems/2.0.0/gems

What version of nokogiri am I installing?

$ ls -ladg nokogiri-*nokogiri-1.5.5

Go to the installer directory:

$ cd nokogiri-1.5.5/ext/nokogiri

Try installing manually:

$ ruby extconf.rb

Result:

checking for libxml/parser.h... *** extconf.rb failed ***...

I'm using Ubuntu so I search for any similar packages:

$ aptitude search libxml

Results:

p libxml2 - GNOME XML libraryp libxml2-dev - Development files for the GNOME XML library...

I believe that libxml2 will work fine.

$ apt-get install libxml2

Ruby native gems often need the *-dev packages for headers so install them:

$ apt-get install libxml2-dev

Now do I have the parser file?

$ find / | grep libxml/parser.h

Yes, the result shows the parser:

/usr/include/libxml2/libxml/parser.h

Now try installing again, this time providing the libxml2 path:

$ gem install nokogiri -- --with-xml2-dir=/usr/include/libxml2

It still fails, so read the mkmf error log:

$ more mkmf.log 

The error log shows what failed and has these lines that look promising:

package configuration for libxslt is not found

Is there a package for it?

$ aptitude search libxslt

Results:

v   libxslt-devi   libxslt-ruby...

Install the dev package:

$ apt-get install libxslt-dev

Now try installing again, and also put xslt on the path:

$ gem install nokogiri -- \--with-xml2-dir=/usr/include/libxml2 \--with-xslt-dir=/usr/include/libxslt

Success!

Installing Nokogiri Website

'Installing Nokogiri' is a website dedicated to installing Nokogiri on the major platforms - Here is an excerpt about Installing Nokogiri on Ubuntu:

Because Nokogiri needs to be compiled and dynamically linked against both libxml2 and libxslt, it has gained a reputation for being complicated to install.

As of Nokogiri 1.6, libxml2 and libxslt source code is bundled with Nokogiri, and compiled at gem-install-time. The instructions in this document should work for all versions 1.6.4 and later.

Ubuntu / Debian

Installation should Just Work™ on Ubuntu and Debian using Nokogiri’s vendored libxml2 and libxslt:

gem install nokogiri

[...]

Using Your System Libraries

If, instead of Nokogiri’s vendored libraries, you’d like to use your system’s libxml2, libxslt and related libraries, please first understand that you may be asking Nokogiri to work with an unsupported version of libxml2.

sudo apt-get install pkg-configgem install nokogiri -- --use-system-libraries

FYI - I am using Nokogiri 1.6.6.2 and it didn't 'just work'. I got it going with the --use-system-libraries.

Mac OS X

The website's advice also covers OS X - this worked for me:
gem update --systemxcode-select --installgem install nokogiri

Conclusion

If you have a Nokogiri problem on any platform you should check out the website.

On CentOS here is what I needed to do:

gem update --systemyum install libxml2-devel libxslt-devel ruby-develgem install nokogiri -- --use-system-libraries