じゃあ具体的にどうすればいいのかという話だけど、お勧めは次の方法だ。
まず次のように標準出力を適当なエンコーダで包む。

import codecs
Writer = codecs.getwriter(sys.getfilesystemencoding())
stdout = Writer(sys.stdout)

その上で print 文をすべて次のように書く。

print >>stdout, '"total","%s",%d' % (root, dirsize[root])

この例ではリダイレクトしているか否かに関わらず sys.getfilesystemencoding() の返す
エンコーディングでエンコードするようにしている。このエンコーディングは、俺の知る限り
標準出力がリダイレクトされていない場合の sys.stdout.encoding と一致している。
sys.getfilesystemencoding() を使う代わりに、例えば cp932 に決めうちしちゃうとか、
コマンドライン引数で出力エンコーディングを指定するようにするといった方法も考えられる。
標準出力リダイレクト時のエンコーディングをどうするかは用途に強く依存する問題なので
こればかりはプログラムを書く人（つまり197さん）が決めるしかない。