When using PyInstaller to package my PySide application  i had following errors in the command-line:

3513 INFO: Looking for dynamic libraries
3663 ERROR: Can not find path ./libpyside-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtGui.so)
3664 ERROR: Can not find path ./libshiboken-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtGui.so)
3670 ERROR: Can not find path ./libpyside-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtNetwork.so)
3670 ERROR: Can not find path ./libshiboken-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtNetwork.so)
3680 ERROR: Can not find path ./libpyside-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtCore.so)
3680 ERROR: Can not find path ./libshiboken-python2.7.1.2.dylib (needed by /Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PySide/QtCore.so)

My application did start on my own machine but not on others where PySide was not installed. Here is a simple fix which worked for me to get my app running on another mac:

Open following file:

/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/PyInstaller/depend/bindepend.py

and look for the function _getImports_macholib()… inside that function find following loop:

# Try multiple locations.
for run_path in run_paths:
    # @rpath may contain relative value. Use exec_path as
    # base path.
    if not os.path.isabs(run_path):
        run_path = os.path.join(exec_path, run_path)
    # Stop looking for lib when found in first location.
    if os.path.exists(os.path.join(run_path, lib)):
        final_lib = os.path.abspath(os.path.join(run_path, lib))
        rslt.add(final_lib)
        break

and change the loop to

# Try multiple locations.
for run_path in run_paths:
    # @rpath may contain relative value. Use exec_path as
    # base path.
    if not os.path.isabs(run_path):
        run_path = os.path.join(exec_path, run_path)
    # Fix path problems for PySide install on OSX
    if "PySide" in run_path:
        run_path = run_path.replace("../../../", "") 
    # Stop looking for lib when found in first location.
    if os.path.exists(os.path.join(run_path, lib)):
        final_lib = os.path.abspath(os.path.join(run_path, lib))
        rslt.add(final_lib)
        break

That's it, save the file and package your app. For me that fixed all other errors.

Here my setup when fixing: PySide 1.2.4 (PyPi), Qt 4.8.7 (stock binary), Python 2.7.12, PyInstaller 3.3-dev

Happy coding.