この前、フォルダ丸ごとパスワード付zipにするコマンドラインツールを作ったとき、
ICSharpCode.SharpZipLib.dllを使いました。
http://www.icsharpcode.net/OpenSource/SharpZipLib/Download.aspx
Imports ICSharpCode.SharpZipLib.Zip
Dim fz As New FastZip
Dim zipfile As String = "C:\BBB.zip"
Dim srcpath As String = "C:\aaa\bbb"
fz.Password = "password"
fz.CreateZip(zipfile, srcpath, True, "", "")