さくらのVPSのデフォルトのOSはCentOS 5になってます。VPSコントロールパネルから他のOSのインストールもできるようですが、そもそもコンソール機能があるので普通にいろいろなOSをインストールすることが可能です。
といわけでCentOSの最新版であるCentOS 6.0を使うことにしました。CentOS 6はリリースまでにすごく時間がかかったり、主要な開発者であるDag Wieersが開発から離脱したり（あのDAGですよ？）、先行きが不安なところもあるかもしれませんが、他にこれといった選択肢もないので、ここではとにかくCentOS 6.0をインストールすることにします。
インストール手順については、ずばり以下のサイトにあります。
上のサイトにもありますが、ネットワークの設定はメモって置く必要があります。最悪忘れてしまってもデフォルトのCentOSを再インストールすると確認できます（５分程度です）。共通の設定項目についてはマニュアルにも載っています。DNSサーバの設定が実際と違っていたのが若干気になりますが。
インストールは選択肢も特になくすぐに終了します。普通にインストールしたときにはディスク構成やパッケージなどもう少し選べるところがあった気がしますが、シリアルコンソールからのインストール専用のメニューなのかもしれません。
インストールが終了するとあとは普通に使うことができます。とりあえずアップデートをあてて、あとは必要なパッケージのインストールともろもろの設定を行っていくことになります。