C#でzipファイルを解凍する方法は幾つかあるようですが
以下の条件で絞って探してみました。

・Framework2.0以降で利用できること
・とにかく簡単なこと
・J#などに依存しないこと

2011年7月の現時点ではオープンソースで開発されている
DotNetZip ライブラリを利用するのがお手軽そうです。

まずは DotNetZip のサイトより
必要なランタイムDLLをダウンロードしてください。

DotNetZipトップページはこちら

トップページを開いたら Downloads タブを選択します。
ファイルが何種類か並んでいますが
とりあえず必要なのはランタイムのみなので

DotNetZipLib-Runtime-v1.9.zip

のようにランタイムが圧縮されたファイルをダウンロードし
適当なフォルダに解凍してください。
（バージョン番号やファイル名は今後変更されると思います）

展開すると以下のような階層で色々入っていますが
開発に必要なのは※印の付いた
DotNetZip-v1.9 フォルダの Ionic.Zip.dll ファイルです。

    │  Contents.txt
    │  License.txt
    │  PleaseDonate.txt
    │  Readme.txt
    │
    ├─DotNetZip-Reduced-v1.9
    │      Ionic.Zip.Reduced.dll
    │      Readme.txt
    │
    ├─DotNetZip-v1.9
    │      Ionic.Zip.dll ※これを使います
    │      Readme.txt
    │
    ├─DotNetZip-v1.9-CompactFramework
    │      Ionic.Zip.CF.dll
    │      Readme.txt
    │
    ├─zlib-v1.9
    │      Ionic.Zlib.dll
    │      Readme.txt
    │
    └─Zlib-v1.9-CompactFramework
            Ionic.Zlib.CF.dll
            Readme.txt

次に、Ionic.Zip.dll ファイルを
プロジェクトの参照設定に追加してください。

やり方は幾つかありますが
１．ソリューションエクスプローラーの参照設定を右クリックして参照の追加
２．参照の追加Dialogが開いたら参照タブより上記ファイルを選択

あとは下記サンプルコードを参考にしてください。
数行のコードで解凍が可能です。

もちろん、アプリを実行する際は
Ionic.Zip.dll ランタイムも必要になるのでお忘れなく。
ライセンスも最新情報を確認しましょう。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Ionic.Zip;    // usingを忘れずに
using Ionic.Zlib;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            // zipファイル読み込み
            ZipFile zip = new ZipFile(@"c:\sample.zip", Encoding.GetEncoding("shift_jis"));

            // 展開する。すでにあれば上書きする。
            zip.ExtractAll(@"c:\", ExtractExistingFileAction.OverwriteSilently);

            // 後始末。面倒ならusingしておいてもおｋ
            zip.Dispose();
        }
    }
}