Disclaimer: I just started to explore this topic myself, so what follows could be wrong. I have tested very little of what follows.
They both prepare a Python app for distribution.
Also known as freezing.
general purpose vs special purpose
pyinstaller works with many Python apps that use many Python packages, not necessarily PyQt (although it works with PyQt.)
pyqtdeploy is for Python apps that use PyQt (and thus Qt). Apps can use other Python packages, but they must use PyQt.
Static versus dynamic linking
pyinstaller uses dynamic linked libraries. pyinstaller archives said libraries and fiddles with environment variables so that the frozen app (which is really a boot loader that forks to a Python interpreter which interprets your app) finds the archived libraries instead of any other libraries of the same name on the destination computer.
pyqtdeploy statically links libraries into one big executable. Again, the executable is basically a Python interpreter interpreting your app, but it all loads at once when the app starts.
pyinstaller discovers the Python packages your app uses.
pyqtdeploy requires you to tell it the same information (in a GUI interaction.)
pyinstaller seems stuck at Python version less than Python 3. (The project is working at supporting Python 3, but they are not there yet.)
pyqtdeploy freezes Python2.6 or Python3 apps, but requires Python3 to run.
pyinstaller supports the desktop platforms (Linux, OSX, Win). pyinstaller is not a cross compiler.
pyqtdeploy supports the same, and also the major mobile platforms (iOS and Android) (although, currently you must do much work yourself i.e. cross compile libraries for the mobile platforms. pyqtdeploy might get better in this regard?)
Project organization and licensing
pyinstaller seems to be an open source project with several contributors.
pyqtdeploy is open source but seems to be mainly the contribution of one person. PyQt itself is licensed for GPL use, but has a commercial license for non open source use. Since pyqtdeploy depends on PyQt, it really depends on the licences or PyQt (no matter how pyqtdeploy is licensed.)