I have yet to fly anywhere since 9/11, but I'm working on a plan based on what others have said and on what I want. Here it is:

1. Carry-on underseat bag with migraine meds and other medical essentials such as Mylanta, Exedrin, earplugs, etc.
2. Small carry-on for bin-storage. This holds a day or two worth of clothes and other small items.
3. Medium carry-on to be checked. This will hold clothing and an inexpensive version of my EDC, including easily replaceable Swiss Armys and such.
4. Another medium (duffle?) bag for FedEx-ing. This will hold the rest of my stuff and my full-bore EDC.

Bags 3 and 4 above are likely to be small to medium carry-on types. I'd rather not combine them into one larger, more unwieldy bag.

-- Craig