I would use Photoshop to do the cut outs. Photoshop has really handy tools (like content-aware fill) which you will want to use! There are some handy tutorials over on VideoCopilot.net for doing this exact thing.
Absolutely do it in Ps. I use the technique a lot, I find I need a specific type of image for it to work well. I find it works best to have three distinct planes, ideally with the subject in the midground, and be amenable to filling the holes you need to patch in the background with content aware fill or some cloning other technique and a little bluring. And lots 'o depth of field don't hurt. And the image needs to be grande. Too many pixels is not enough...
Some photos can easily be split into layers in AE but most of the time you'll need to fill in some holes and Photoshop is by far the best app for that. You can also use 3D layers and camera projection for some shots. I do that quite a lot. This tutorial by my friend Andrew Kramer, though a bit long winded, shows how to do camera projection and it works very well on some images. 3D Camera Projection - VIDEO COPILOT | After Effects Tutorials
This script makes camera projection really easy when you need to combine video and still images. Projection - aescripts + aeplugins - aescripts.com
You can also just cut out segments of some videos in AE using the mask tools, but as I said in the first paragraph, most of the time you'll need to fill some holes. The easiest way to do that by far is to shoot a clean plate first before you move your actors into position. The next easiest way to do that is to prepare your images in Photoshop before you bring them into AE.