The state flown over the most actually is…Virginia.
Next in line are Maryland, North Carolina, and Pennsylvania.
In part this is because so many flights from the very busy Atlanta airport cross Virginia. Yet the airport with the most flights above Virginia is Toronto, including most of its flights to the Caribbean and Latin America.
Other than Hawaii, the least flown over state is — surprise — California. Hawaii is also the “most flown under” state, if you look at the opposite point on the globe. Most of the continental U.S. “opposites” into obscure parts of the Indian Ocean, but Hawaii opposites into Botswana.
That is all from Randall Munroe’s What If?: Serious Scientific Answers to Absurd and Hypothetical Questions.