I looked into how starlings do this. The answer being, we don't really know. This article from Wired was just published yesterday:
I checked my usual science blogs and none of them had posted anything about it. Carl Zimmer, where are you when we need you, man? So the article essentially speaks for itself. The birds overall behavior looks more like boiling water than animal behavior. But what does that mean?
What I think it means is that the birds have some way of sensing what's going on with many if not all the other birds around it that we don't understand. Behaviors don't just happen so unless starlings are actually some kind of future alien robots with quantum computing capabilities in their brain that allow them to sense things free from the bonds of time and space they must be "communicating" in some way.
It reminded me, initially, of schooling fish. Fish all have a sensory organ called the lateral line (the next time you see a fish take a look at it's side: many have a visible line down the middle. Cod, for example, have a very noticeable lateral line). The "organ" is actually a series of mini-organs, pits with sensitive hair-like structures that sense pressure differentials (i.e. moving water). Because the fish can sense differences in pressure so acutely they "know" what the movement of their neighbors and their neighbors neighbors is like and can adjust their movement accordingly.
Now birds don't have lateral lines...they are derived bony fish, though, so maybe...
It reminded me of another natural history story, though. Dolphins can do something really odd. When a trainer has worked with them the human can ask a pair of dolphins to do a novel behavior together. Without making any detectable sounds the dolphins will swim to separate parts of a pool and do a behavior neither of them has ever done before at the same time. And we have no idea how this happens. We assume the dolphins must be communicating. We just have no idea how. All of our attempts at measuring the communication have failed.
We tend to assume things with animals will be nice and easy, that they won't do things that defy our recording equipment or appear more like particle physics but then something like this comes along like this. I'm betting this won't be resolved for a long while, usually some scientist has to really overcome the standard thought about how things might be working to solve a problem like this. And it'll probably be really cool science when that person comes along.