Debianのrubyだとmkmfとか標準で入ってないらしい

Hpricotを試してみようと思ってインストールしていたらmkmfがないと言われた。

ruby1.8-devパッケージをインストールして解決できました。

Cの拡張ライブラリを入れる際にはmkmfがないとインストールできないので注意されたし。