Paul, can't speak directly to CS4, but you import into AE via XML export (Export to AE) out of media 100. Comes in with the edits as they appear in your timeline, but with the full handles of your original media. If you are running on AE on a separate system, there are a few more steps, but its not too much.
Additionally to what Jim said, you need to make sure that the AE Project importer for CS4 is installed. Unfortunately this is only shipping with Media 100 suite V1, and I am not 100% sure that it will work with projects exported from Media100 V13.x.
To give it a try, first, rename your AdobeAfterEffects Plugin folder within your Media100 folder to e.g. "AEPlugin Version 13". Then download the Media 100 Suite trial version. Then right-click on the installer on the disk image and select "show package content". Within this installer there is a folder named Content->Packages, with a file named Media100Suite1SpecialFolders.pkg. Run this installer and let it place the new AE folder within your Media 100 folder.
Then copy the "AE_XML_Project_Importer.bundle" from the new AE exporter folder within your Media100 folder into YourAdobeAfterEffectsCS4 folder->Plugins->Format. Then try to import the file that you exported from Media100 via the File->Export to AfterEffects command.
If this does not work you either can upgrade to Media 100 Suite, or you can use the AE CS3 workaround. Export to AE from Media 100 as before, copy the AE_XML_Project_Importer.bundle from your Media 100 folder into the AE CS4->Plugins->Format folder and import the project there. Save the AE project and open the AE CS3 project in CS4.
I think I will just upgrade to M100 suite. If I do this will the export out of M100 and import into AE (with Handles) be a straight forward thing? Or will I still have to go through some sort of set it up as per your instructions above?
I'd love to see a video tutorial walking dumbies like me through how to set up and use the M100 - AE workflow.