Barbecue, of course, is basically flavored smoked meat, so the major points for distinguishing different styles of barbecue are:
(1) kind of meat
(2) kind of smokiness
(3) kind of flavoring
This is a kind of order of influence as well; the kind of meat affects the kind of smokiness you want, and they both affect the kind of flavoring you want. The major divide on the meat point is Pig or Cow. Other meats are possible, of course, but a regional style will have one dominant, an easily obtained meat that smokes and grills well, and these are the major two contenders, certainly in the US, but also elsewhere. They both smoke well with just about any wood. Poultry, Seafood, and Lamb, the most widely available alternatives, are usually just supplements, with only very rare exceptions; that is, they are meats that you'd usually only smoke and grill if you were already used to that with other meats, and the kind of smoking you do can matter a lot to whether you get an edible result. In the US, we run the gamut from the pork-heavy Carolinas to beef-heavy Texas.
Smokiness is primarily a matter of wood, and roughly arranges itself on two axes, sweet to earthy and subtle to heavy. They are not completely independent; subtle tends to be sweet, heavy tends to be earthy. An example of sweet subtle would be applewood; hickory is heavy but moderate between sweet and earthy, and mesquite is about the edge of what is viable on both heavy and earthy. Hickory is King Smoke because its heaviness means you get the flavor regardless of what else you do, but it is much less earthy than most heavy, so it goes well with almost everything. Pork and beef will handle just about any kind of smoking, but generally beef-heavy styles tend toward heavy and pork-heavy styles tend toward sweet.
One of the original sources of regional styles in the US was the kind of wood that was easily available. The most obvious case of this forcing a divergence is Texas-style barbecue. Large portions of Texas are not exactly heavily forested, and the cheapest easily available smoking wood is mesquite, which grows like a tree's imitation of a weed and is useful for almost nothing else. Thus mesquite is the major influence on the style, although there is actually a lot of variation throughout Texas in how central mesquite actually is.
Kind of flavoring tends to have two axes. The first is sweet and spicy; most barbecue flavoring is a little of both in a tangy base, but the emphasis can be in one direction or another. Spicy styles tend to dominate in most places, but there are always pockets of sweet-toothers. The other axis I generally think of as wet and dry, but this is somewhat misleading, since it's really more like saucy and not saucy. Pure dry rub as a customary style is rare outside of parts of Tennessee; the 'dry' category would include thin-sauce barbecue like that associated with North Carolina (especially western North Carolina) or the Philippines or Korea. The opposite extreme from Memphis-style pure dry rub is thick-sauce Texas-style, which is the sauciest of saucy barbecue. I suppose it's not surprising that when Texas goes for something it goes hard; Texas-style BBQ is so famous because it is highly distinctive, and it is highly distinctive because it is the wettest smokiest beefiest common style. If you want Spicy Wet Heavy Earthy Cow, there is no place in the universe like Texas for it. The reason is the mesquite -- mesquite gives a very strong flavor, so you can add a lot of sauce, relatively speaking, without overpowering the meat, but the earthiness actually makes a good base that allows for a lot of variation in sauce. Another example of wet/saucy would be the mustard-sauce barbecue associated with the South Carolina Midlands. Tennessee dry rub, I assume, arises because Tennessee historically had a lot of access to sweet subtle smoking woods, so going very dry lets you appreciate the smoky side better.
All of these, of course, affect sides, although I think this is a messier matter, because it's common to have a diversity of side dishes to allow for a lot of variation in flavor, texture, and temperature. As far as regional styles go, however, some things dominate, and the reason is sometimes quite straightforward. The primary Texas-style BBQ side is potato salad, and it's easy to see why: sides are to balance the barbecue, and a smoky heavy barbecue will need a lighter, blander side to balance it. A similar reason undergirds the common use of cole slaw. Likewise availability is obviously a significant matter; nobody is surprised that rice and kimchi are popular sides for Korean barbecue. There are others where the story is less obvious; although in most cases it traces back to style and availability, there's a lot of room of historical accident in slides. While it's clear why slaw would be used, I'm not sure why red slaw in particular is such a major side in North Carolina, for instance, and while it's clear why a potato-based side would be popular in saucy Kansas, I have no idea why it tends to have with french fries rather than potato salad. No doubt there is some story for how these things become locked in.
Of course, these days, you can find almost all styles almost everywhere.
