As someone who lives in Holland and who regularly goes to New York to visit his family, I can tell you right now that any flying with a small child is going to be problematic. With my first child, we took her on a plane when she was 4 months old (for a 4 hour flight to Israel, for a friend's wedding), and then when she was 9 months old (to New York, when my father suddenly passed away).
The short answer to your question is that in theory, even babies only a few weeks old can fly on an airplane, but there are a lot of things to think about (forgetting about the germs that fly around in the circulated air, which is also something to think about if your child is sensitive to that sort of thing):
1) Bring toys to keep your child entertained. You won't be able to keep them completely focused on the toys for the duration of the flight, but it'll help distract them when they start to get fussy.
2) Bring a car seat with you on the plane, especially if the flight is longer than a couple of hours. Yes, you may have to pay for an extra seat, but guess what - you're going to be doing that sooner or later anyway. And by bringing a car seat with you, you assure yourself that you have a safe place for your child to sit while you look for the pacifier or bottle in your carry-on.
3) Check your stroller in. Some airlines will allow you to check this in without hitting you with an extra baggage fee. The only thing to worry about - the stroller will either be the first thing waiting for you as you get off the plane, or the LAST thing they get off the plane (I had both happen to me at one time or another).
4) Breast-feed or give a bottle when taking off and landing. Supposedly this helps alleviate some of the air pressure problems your child might get. If nothing else, by feeding your child when you're about to take off, you might be able to buy yourself an hour of rest before you have to entertain your baby again.
5) Accept that some people are going to be pissed, and do what you have to do when you bring your child on a plane. I once walked up and down the aisle with my daughter in my arms in an effort to comfort her in the middle of the flight. There were quite a few angry looks, but that's all that they can do (at least without facing arrest on landing).
6) Ask the attendants for help when necessary. Most attendants will have no problem giving you extra hot water to heat up your formula, for example.