This is probably not the answer you want to hear, but it is the only real answer to your question. Practice. That's how they did it. They practised and practised until they could do it. The answer really is that simple.
The only other piece of advice I could give you on how to begin to learn to do this is. Learn to control your gag reflex.
