How to measure the distance (in generalized sense) between geographical regions?
In terms of interaction data, you might be thinking of this paper and this project

I love the idea of using flight data. You could start with this set hosted at Kaggle.

In terms of estimating distance between states, the simplest thing you could do that might work is to measure the distance between state capitals.