Is it possible to deploy a Python application on the Mac App Store?

Does Apple accept Python applications for distribution on the new Mac App Store?

If so, how should the application be packaged? Is py2app sufficient? Something else?

I packaged Pennywise, which is available on the Mac App Store. It's based on Virgil's moneyGuru, which uses Python, PyObjC, and py2app.

You will have to follow Apple's process for preparing an application for submission to the Mac App Store. Most importantly, you will want to add the proper keys to your Info.plist, and remove any automatic updating mechanism, e.g. Sparkle. It's not strictly required, but you will probably also want to implement receipt checking. Using Xcode will make the submission process much easier. You can look at the moneyGuru source code for an example of how to use Xcode as the final part of the build process.

Py2app embeds a copy of the Python framework in the bundle, so I don't know whether Apple would approve an application that only linked to the system framework. While the primary binary can't support PPC, Apple does not seem to check the architectures of binaries in embedded frameworks.

One final caveat: I wouldn't recommend this process for writing new applications. Using Python, PyObjC, and py2app seriously complicates the build process and introduces additional dependencies.

I know it's possible because I know of at least one Python-based app that is in the app store ("Pennywise", which is based on my own app, moneyGuru, which uses Python + PyObjc + py2app). I didn't do it myself, so I'm not sure of the details.