I tried both for a current project and decided to use cx_freeze. I found it easier to get started. It has an option to bundle dependencies in a zip archive, which makes it easy to check that everything was properly included.
I had trouble getting PyInstaller to include certain egg dependencies. It couldn’t handle conditional imports as well as I needed and looking through the bundled archive was difficult. On Windows, it requires pywin32 (so it can’t be used with virtualenv) and version 1.4 doesn’t work with Python 2.6. There’s no information on whether Python 2.7 is supported.