結論1

require 'nokogiri'
require 'open-uri'

doc = Nokogiri::HTML.parse(open(url, "r:Shift_JIS").read)
doc = Nokogiri::HTML.parse(open(url).read, nil, "Shift_JIS") #別解1
doc = Nokogiri::HTML.parse(open(url), nil, "Shift_JIS") #別解2

結論2

（2014/11/4追加）
サイト中のテキストに Windows の機種依存文字が含まれている場合は Shift_JIS 指定だと Nokogiri が（正確には Ruby が）解釈に失敗してパースし損ない、 Nokogiri オブジェクトが途中で切れてしまいます。ので CP932 を指定する必要があります。
よって、Shift_JIS エンコーディングの Web サイトに対しては念のために CP932 を指定したほうが良いと思われます。（同様に日本語 EUC エンコーディングの Web サイトに対しては念のために CP51932 を指定したほうが良いと思われます。）

require 'nokogiri'
require 'open-uri'

doc = Nokogiri::HTML.parse(open(url, "r:CP932").read)
doc = Nokogiri::HTML.parse(open(url).read, nil, "CP932") #別解1
doc = Nokogiri::HTML.parse(open(url), nil, "CP932") #別解2

エンコーディングの変換ミスが生じる場合（変換ミスは生じないないと思いますけど）には、文字列オブジェクトに .encode("UTF-8") メソッドを付けて先に UTF-8 に変換しておけば良いと思います。

`Encoding::CP932` とは

（2014/11/4追加）

Windows_31J -> Encoding
CP932 -> Encoding
CSWINDOWS31J -> Encoding
CsWindows31J -> Encoding
WINDOWS_31J -> Encoding
PCK -> Encoding
SJIS -> Encoding
Windows-31J 、Windows で用いられる、シフト JIS 亜種で、 CP932 とも言います。
7bit 部分が論理的には US-ASCII であり、また Windows の機種依存文字を扱うことができます。
るりま：constant Encoding::CP932

`Kernel.#open` でのエンコーディング指定

（2014/11/4追加）

open(file, mode_enc = "r", perm = 0666) -> IO

open(file, mode_enc = "r", perm = 0666) {|io| ... } -> object

file をオープンして、IO（File を含む）クラスのインスタンスを返します。
[PARAM] mode_enc:
モード・エンコーディングを文字列か定数の論理和で指定します。

open(name, mode = 'r', perm = nil, options = {}) -> StringIO | File [redefined by open-uri]

open(name, mode = 'r', perm = nil, options = {}) {|ouri| ...} -> nil [redefined by open-uri]

name が http:// や ftp:// で始まっている文字列なら URI のリソースを取得した上で StringIO オブジェクトとして返します。
[PARAM] mode:
モードを文字列で与えます。Kernel.#open と同じです。

第二引数のオープンモード・エンコーディング

文字列(mode か mode:ext_enc か mode:ext_enc:int_enc という形式)（中略）指定します。

エンコーディングの指定

ext_enc (外部エンコーディング)が指定されている場合、読み込まれた文字列にはこのエンコーディングが指定され、出力する文字列はそのエンコーディングに変換されます。
int_enc (引用者註：内部エンコーディング)も指定されていた場合、入力された文字列を ext_enc でエンコーディングされた文字列とみなして int_enc へと変換し、その結果に int_enc を設定して返します。
るりま：module function Kernel.#open

open-uri でエンコーディングを指定していない場合には Content-Typeをみる

エンコーディング引数がない場合、レスポンスヘッダの Content-Type の charset をそのままセットしようとします。

Ruby1.9のNet::HTTPで取得した文字列はforce_encodingせざるを得ない - きたももんががきたん。

それでも解釈できなかった場合、文字列のエンコーディングはバイナリ（ASCII-8BIT）になります。

open-uri では内部エンコーディングの指定が利かない

結論1は、当初

doc = Nokogiri::HTML.parse(open(url, "r:Shift_JIS:UTF-8").read)

と書いていました。しかし Shift_JIS なサイトを読み込んだ際に

open(url, "r:Shift_JIS").read.encoding
#=> #<Encoding:Shift_JIS>
open(url, "r:Shift_JIS:UTF-8").read.encoding
#=> #<Encoding:Shift_JIS>

となり、 open-uri では内部エンコーディングの指定が利かないことに気付きました。（ open(file) であれば内部エンコーディングが利くんですけど。）
ということで、内部エンコーディングの指定を外しました。

`Nokogiri::HTML.parse` でのエンコーディング指定

parse(thing, url = nil, encoding = nil, options = XML::ParseOptions::DEFAULT_HTML, &block) ⇒ Object

Parse HTML. Convenience method for Nokogiri::HTML::Document.parse
Method: Nokogiri::HTML.parse — Documentation for sparklemotion/nokogiri (master)

Nokogiri::HTML.parse の第3引数で、 thing （StringIO または String）のエンコーディングを文字列で指定します。 Encoding クラスの定数での指定は出来ません。

エンコーディングリスト

（2014/11/4追記：当初は Encoding.list で得られるエンコーディングのオブジェクトの名称をリストしていましたが、 Encoding.name_list だと更にエイリアスも含まれる（参考：Rubyist Magazine - Ruby M17N の設計と実装 - エンコーディングの取得）とのことなので変更しました。）

Ruby 1.9.3p547 の場合

> puts Encoding.name_list.sort.join("\n")
646
ANSI_X3.4-1968
ASCII
ASCII-8BIT
BINARY
Big5
Big5-HKSCS
Big5-HKSCS:2008
Big5-UAO
CP1250
CP1251
CP1252
CP1253
CP1254
CP1255
CP1256
CP1257
CP1258
CP437
CP50220
CP50221
CP51932
CP65000
CP65001
CP737
CP775
CP850
CP852
CP855
CP857
CP860
CP861
CP862
CP863
CP864
CP865
CP866
CP869
CP874
CP878
CP932
CP936
CP949
CP950
CP951
EUC-CN
EUC-JP
EUC-KR
EUC-TW
Emacs-Mule
GB12345
GB18030
GB1988
GB2312
GBK
IBM437
IBM737
IBM775
IBM850
IBM852
IBM855
IBM857
IBM860
IBM861
IBM862
IBM863
IBM864
IBM865
IBM866
IBM869
ISO-2022-JP
ISO-2022-JP-2
ISO-2022-JP-KDDI
ISO-8859-1
ISO-8859-10
ISO-8859-11
ISO-8859-13
ISO-8859-14
ISO-8859-15
ISO-8859-16
ISO-8859-2
ISO-8859-3
ISO-8859-4
ISO-8859-5
ISO-8859-6
ISO-8859-7
ISO-8859-8
ISO-8859-9
ISO2022-JP
ISO2022-JP2
ISO8859-1
ISO8859-10
ISO8859-11
ISO8859-13
ISO8859-14
ISO8859-15
ISO8859-16
ISO8859-2
ISO8859-3
ISO8859-4
ISO8859-5
ISO8859-6
ISO8859-7
ISO8859-8
ISO8859-9
KOI8-R
KOI8-U
MacJapan
MacJapanese
PCK
SJIS
SJIS-DoCoMo
SJIS-KDDI
SJIS-SoftBank
Shift_JIS
TIS-620
UCS-2BE
UCS-4BE
UCS-4LE
US-ASCII
UTF-16
UTF-16BE
UTF-16LE
UTF-32
UTF-32BE
UTF-32LE
UTF-7
UTF-8
UTF-8-HFS
UTF-8-MAC
UTF8-DoCoMo
UTF8-KDDI
UTF8-MAC
UTF8-SoftBank
Windows-1250
Windows-1251
Windows-1252
Windows-1253
Windows-1254
Windows-1255
Windows-1256
Windows-1257
Windows-1258
Windows-31J
Windows-874
csWindows31J
euc-jp-ms
eucCN
eucJP
eucJP-ms
eucKR
eucTW
external
filesystem
internal
locale
macCentEuro
macCroatian
macCyrillic
macGreek
macIceland
macRoman
macRomania
macThai
macTurkish
macUkraine
stateless-ISO-2022-JP
stateless-ISO-2022-JP-KDDI

Ruby 2.0.0以降

上記に

EUC-JP-2004
EUC-JISX0213

が追加されています。

参考

Rubyist Magazine - Ruby M17N の設計と実装
Ruby - Nokogiriで文字化けを防ぐ - Qiita
Ruby - CSV を文字コード変換しつつロード - Qiita
[ヅ] Ruby 1.8系と1.9系で文字エンコーディング変換 (2011-05-05)
Shift_JIS 文字コード表 ← <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=shift_jis"> タグが含まれています。 Windows 機種依存文字が含まれていますので CP932 を指定すれば読み込めます。

Shift_JISサイトをNokogiriでパースするときにはエンコード指定（CP932指定推奨）

結論1

結論2

Encoding::CP932 とは

Kernel.#open でのエンコーディング指定

第二引数のオープンモード・エンコーディング

エンコーディングの指定