By "reasonable" environment I mean that it should not require the user to manually install any dependencies of the application, but a working Python installation can be required. Additionally I would like the application to work on Windows, OSX, and popular Linux distributions. If I can package a Python interpreter as well, that's better. Size is not really a concern. A good example of what I want to accomplish is the SublimeText editor. 
Is there an established way of doing this?
Yes, python comes with setup utilities, and there are packages which will put your complete application in a platform specific binary(exe on windows, .app on osx).
Some of the packages I would recommend looking at would be:
cx_freeze
py2app
py2exe
How can I create a package of a PyQt/PySide application which can be expected to run in "reasonable" environments?