First introduced (at least under its current incarnation) by crypto- and computer security-guru Bruce Schneier, attack trees are a way to get smart about the anticipation of, and defense from, attack. Though he designed them primarily for modelling computer and network based threats, it should be clear that they serve equally well in almost any other situation.
The construction of an attack tree, at least on the surface, is simple. You place at the top of the tree the goal of an attack (in a case where your system may be subject to multiple attacks with entirely different motivations, you might need several trees). Branching off of this are all the ways you (and whenever possible, several other very smart people) can imagine someone might obtain this goal. If those methods would in turn require other intermediate steps, then under each of those subnodes, branch off as appropriate.
The example Bruce uses here, which I will borrow shamelessly, is that of opening a safe. Placing "Open Safe" at the top of this simplified tree, he branches out under it "Pick Lock," "Learn Combo," "Cut Open Safe," "Install Improperly." No doubt there are several more, but for example purposes, this will do. The "Learn Combo" sub-goal can be accomplished in several ways and so under it branch off nodes for "Find Written Combo" and "Get Combo from Target." In fact, the "Get Combo from Target" sub-sub-node branches too, since there are many methods, of varying legality for accomplishing this, but I hope that by this point, the method for tree construction is clear.
Once such a tree has been constructed, the next step is to begin identifying viable paths. Bruce suggests either labelling nodes with "Possible"/"Impossible", or in a more sophisticated (to say nothing of more pragmatic) model, to label each node with its estimated cost; in time, money, or whatever else is of critical importance. Once this is done, any path from a bottom level node to the goal is a potential attack. If any of the nodes are marked "impossible" or "infinite/unacceptable cost", then paths passing through that node are disallowed. If a path remains, and most of the time several will, then presto - there's your list of possible attacks. If you're on the defensive side of one of these trees, then this is your list of things against which you should be defending yourself.
This construct has several properties of note. First among them is that it gives one a much clearer sense of the possible attacks a system might face. Without attack trees, or some equally helpful alternative, a person charged with defending a system must essentially just sit there racking their brain to come up with a big list of attacks, and their component elements. Such a list might include just as many attacks, but the attack tree provides one with a way to visualize it; to find choke points; to plan an intelligent defense.
What I think is the bigger asset though, is the way in which an attack tree is necessarily goal-focused. Defense strategies, for computer systems, or anything else, are very often attack-focused: a company trying to protect accounting reports will audit their web server, close down telnet and make sure it's firewall is top-notch... and then forget to shred accounting department printouts and toss them in a dumpster. The company wasn't wrong to secure their web servers, but they were focusing on a possible attack, not on the attack's goal. By understanding things from a goal-oriented perspective, they ask "if I wanted to obtain accounting documents, how could I do it?" Now they're thinking like the attacker, which is the only way to set up any respectable defense at all.
The design of attack trees, while incredibly helpful, is something of an acquired art. It can't be done automagically, despite it's apparently formal structure, because it requires people to think about all the possible attacks. The attack tree helps by getting people focused on the right things, but it still takes time and ingenuity to develop a knack for fleshing out a complete attack tree, which can contain hundreds, maybe thousands of attack paths and sub-sub-sub-nodes.
Sometimes it's even hard to figure out what the right goals should be. Even Bruce's example seems a little suspect in this regard - is the goal really to open the safe, or to read some particular document? If the latter is the case, then opening the safe is really just one sub-node in the larger tree whose goal is "read a particular document." This reasoning can be over-extended though: "read a particular document" might just be part of the higher goal "find embarassing information about the competition," which in turn might just be a sub-sub-node on the "Make money" tree, which is subsumed under the "Find happiness" tree. If you over-generalize, the tree either becomes unmanageable, or unhelpful in short order. Knowing when to stop is also part of the art of attack-tree construction, but with some practice, the attack tree model becomes an indispensable aid.
One immediate criticism of attack trees that may be offered up is that they rely on the defender to anticipate the attacker's thoughts, that if the defender misses something, a clever attacker could sneak through. This is almost entirely true, but also irrelevant. It is almost entirely true because it is indeed the case that unanticipated attacks can't normally be defended against, however it is possible that by using an attack tree, the defender will close off certain high-level choke points which make some unanticipated attacks non-viable as well. It is irrelevant though, because this criticism applies equally well to almost any other defense strategy - it is the eternal military truth that defenders have it rough - they have to think of everything, attackers only have to find one hole. Sucks to be a defender, I guess, but this isn't a fault of attack trees.
Since Bruce Schneier seems, at least, to have introduced the concept, he is probably the best equipped to describe it. He does so in his book Secrets & Lies, but also provides an online paper originally written for Dr. Dobb's Journal which, at time of writing, could be found at http://www.counterpane.com/attacktrees-ddj-ft.html.