NEVER too soon!
Our first trip we traveled with an almost 3 year old, almost 2 year old and an 8 week old. Plus friends had a almost 2 year old, and 12 week old.
Let me tell you, the easiest two from that trip were the babies! I was only nursing, which made it a breeze. She ate whenever she wanted, and I wore her from morning to night. I would wake up, stick her in the sling, and take her out to eat, change diapers and put her back in. She was the happiest thing, and all the characters loved her! Mary poppins offered to babysit!
THe older one were great too, just much more work. My 8 week old was not sleeping through the night, but once again, she nursed and slept in the bed with me while we were gone. It was easy!