I currently develop an application which is written in C++. For scripting purposes I use Python 3.2, which is fine -- on my developer machine with Python installed and all the DLLs in the right place.
I deployed "pure" Python applications (i.e. without native code) before using the excellent py2exe, but I don't have a first clue how to deploy this with an embedded Python.
From what my gut says I suppose the following components are necessary:

Python3.dll & Python32.dll
The .pyd files from Python's "DLLs" directory
The Python library

And the last point is what bothers me: How do I deploy that? That are a few thousand files and I don't really want to copy that around.  Py2exe packs that into a zip-file, I guess I can do something like that in my case too?
And, even more important: How do I tell the Python interpreter at run-time where he finds the library?
From what I recall what you need to bundle depends on what your python scripts call or make use of. If you really only make use of the core intepreter I think you only need to bundle the dll.
Having said that, it shouldn't be too hard to test this on your development box by disabling any paths to your installed python and putting your app and the python dlls and libs into the same test folder.
Deployment of application with embedded Python 3