Preposition choice is complicated and not always logical, but in this case, it appears that both can be used. You fly on an aircraft, so you fly on an airline's aircraft, so (using synecdoche) you fly on an airline. Similarly, you fly with the airline's crew, etc. Note that you can also say
I like to fly American Airlines
even though this sentence could also be interpreted as saying that you are doing the flying, or that you are taking American Airlines out for a fly, etc, the context makes it clear what you mean.
My personal preference is to use on or to leave the preposition out.
The best evidence I can find to demonstrate this is this ngram, where I searched for "flying with * airline" and "flying on * airline"