GUI が本当に単純な場合は、組み込みの tkinter を使用する必要があります。
従うことができるHello, Tkinterチュートリアルがあります。これは非常に簡単です。実行可能ファイルの作成に関しては、py2exe はほとんどの場合問題なく動作するはずです (ただし、tkinter は試していません)。実行可能ファイルを作成する別の方法は、「setup.py」ファイルに特別なパラメーターを追加することです。
setup(...,
entry_points = {"gui_scripts" : ['name-of-executable = name_of_package.launcher:main']})
これにより、たとえば、ターミナルに「name-of-executable」と入力して実行できる実行可能ファイルが作成されます (Python の「scripts」パスが PATH にある場合、Windows でも同様です^^)。「name_of_package」というモジュールで関数「main」を実行します。そうすれば、py2exe を使用する必要はありませんが、Windows インストーラーや Debian パッケージなどを作成できます。
より複雑なプロジェクトの場合は、PyGTKとGladeをインターフェイス デザイナーとして使用することを強くお勧めします。いくつかの Python パッケージをインストールする必要があり、加えて GTK+ をインストールする必要があります (Windows では必ずしも簡単ではありません)。API は素晴らしく、十分に文書化されており、GTK のレイアウトの概念に慣れれば、Glade は非常に使いやすくなっています。しかし、私は PyGTK で複数のプロジェクトを行ってきたので、私の意見は偏っています。wxWidgets または PyQT は良い代替手段です。たとえば、bazaar エクスプローラーは QT を使用して記述されています。