Edit first, then use AE. This means you need Edit Lock before you use AE, or it can turn into a big pain for you. If you use AE on all the footage, you need a LOT more storage than you're using right now, and it'll take AE forever to render footage, especially if you shoot multicam. Not to mention you lose the original time code on the footage.
Okay, I'm using CS6. Don't know if that make a difference. What is "Edit Lock"? So, what you're saying is, edit my video into one file, then break it down shot by shot in AE as needed? Didn't know about the TBC issue. Good to know.
Edit your video before AE, yes. But you don't have to make one video file and re-separate everything. If you use Dynamic Link to bring a Premiere Project in or rendered out an edited video, re-cutting it would be extremely annoying (even if you had a handy script to detect the scene changes for you). Instead, you can choose to import a Premiere Pro project into After Effects and it will bring it in with each cut on its own layer. Very handy.
Edit lock means that you (and whoever is in charge of approving this stuff) agree that no more changes to the edit will be made and thus you are ready for the compositing/graphics/coloring stage.