A binary adder (or sometimes simply adder) is a circuit to add two binary numbers together. It has at least two inputs (for the two numbers) and two outputs, for the output digit, and for carrying. A circuit this simple as the above is actually known as a half adder because you cannot carry into it. A full adder has an additional input for taking carry output. Adding is one of the most important things a CPU does because adding accounts for a significant number of the computer's operations. A CPU without a FPU tends to achieve multiplication by repeated addition, for example. Even subtraction is achieved through addition; See twos complement.
HALF ADDER
There are only four possible states to a half adder. You can add 0+0, 0+1, 1+0, or 1+1, and each produces a different result. This is shown in the truth table below.
INPUTS OUTPUTS
A B CARRY SUM Explanation

0 0 0 0 0+0 = 0 (no carry)
0 1 0 1 0+1 = 1 (no carry)
1 0 0 1 1+0 = 1 (no carry)
1 1 1 0 See below
What happens when we add binary 01 to binary 01? We get binary 10. Since this cannot be expressed in a single binary digit, we carry the overflow from our column to the next. (If we have multiple columns, it's not really an overflow, it's a carry. But anyway.)
The question now is, what gates or logical units do we need to build a half adder? The sum appears to be the result of an XOR (exclusive or) command; 1 if either input is 1, but not both. The carry flag is an AND; if both inputs are 1, then carry will be 1. So our half adder consists of only two items, XOR and AND.
I use * to signify a connection between two wires, and + to signify that a wire is changing direction.
A in __
*\\ `._ Sum
 \\XOR `.____________
 // _,'
+//_,'
 
B in   ____
+ + `. Carry
  AND \_____________
  /
+___,'
This is fine as long as all you want to do is work with a single digit. It works fine for a least significant bit (LSB), too, because we will never carry into it. But for every other digit beyond the first we will need a full adder; an adder into which we can carry.
FULL
ADDER
This makes things considerably more complex because we now have three inputs, which makes for (if you have paid attention in binary "class") eight input states (2^3).
INPUTS OUTPUTS
A B C CARRY SUM Explanation

0 0 0 0 0 0+0+0 = 00 (NC)
0 0 1 0 1 0+0+1 = 01 (NC)
0 1 0 0 1 0+1+0 = 01 (NC)
0 1 1 1 0 0+1+1 = 10 (Carry)
1 0 0 0 1 1+0+0 = 01 (NC)
1 0 1 1 0 1+0+1 = 10 (Carry)
1 1 0 1 0 1+1+0 = 10 (Carry)
1 1 1 1 1 1+1+1 = 11 (Carry)
Now how in sam hill do we handle this? We have only two outputs but we definitely need more than two gates this time around, what with three inputs. But amazingly enough the name of our previous circuit gives us a clue: the half adder. Yes, we can use two half adders to make a whole adder, though we do need to augment it slightly. We want to know about A+B, and then we want to know about A+B added to C. This will give us our sum and carry. With three inputs it is now possible to have both sum and carry set at the same time, as per the truth table above.
A __
*\\ `._ __
 \\XOR `.*\\ `._ Sum
 // _,'  \\XOR `._____________________
+//_,'  // _,'
  +//_,'
   
    ____
B    + `. __
+    AND \\ `._ Carry
    / \ OR `._______
Cin   *___,' / _,'
+ +/_,'
  
  ____ 
 + `. 
  AND \+
  /
+___,'
In words; First we add A and B. The sum comes out on the XOR from that halfadder and the carry appears on the AND. We then add Cin and that sum to produce our actual final sum. If either add operation produces a carry, then we want to have a carry on our output, so we can carry it into the next adder.
How does that work? Well, Consider 0+0 with carry, 0+1 without carry, 1+1 without carry, and 1+1 with carry; This gives us all our unique output states.
 0+0 = 0 with no carry. 0+1 (the carry) = 1 with no carry.
 0+1 = 1 with no carry. 1+0 (the lack of carry) = 1 with no carry.
 1+1 = 0 with carry. 0+0 = 0, this is our second halfadder working. Now we OR the carry from each halfadder and since one of them (the first halfadder) is 1, we carry.
 1+1 = 0 with carry. 0+1 (again, the carry) = 1 without a carry, so our sum is 1, the first carry is 1, and the second carry is 0. We OR carry 1 and carry 2 and come up with a 1 since one of them is true. Hence, we have 1 with carry.
You will notice that it is fairly reasonable to display a halfadder in terms of the entire circuit because it is so simple, there being only two binary functions. A full adder has more than twice as many so it takes up considerably more real estate and is a much more challenging piece of ASCII art. In order to show items like this we place them in a kind of shorthand by grouping circuits into functional units defined by their inputs and outputs. Hence the above diagram can become this:
++
A  FULL  Cout
B  ADDER 
Cin   S
++
ADDING
LARGER
NUMBERS
This allows us to easily draw a number of full adders. Why would we want to do this? Because as previously mentioned, you can only handle one digit with a single adder. This is not exceptionally useful most of the time when we're talking about binary numbers since the highest number you can represent is 1. However, the point of allowing carries (and carry inputs) is that you can chain adders together in the same way that we use positional notation; The carry is, well, carried, and summed into the total.
++
A  FULL  Cout (To overflow)
B  ADDER 
Cin +  S (Bit 3/MSB)
 ++

++

++ 
A  FULL + Cout
B  ADDER 
Cin +  S (Bit 2)
 ++

++

++ 
A  FULL + Cout
B  ADDER 
Cin +  S (Bit 1)
 ++

++

++ 
A  FULL + Cout
B  ADDER 
Cin   S (Bit 0/LSB)
++
This is a four bit adder. It will add two four bit binary numbers together and provided the result is not more than 15 (1111 in binary) it will provide a correct answer. We use the carry on the most significant bit of the adder to signify overflow, which is to say, when the sum of the add is too great to represent (or in fact add correctly) with the hardware available to us.
References:
 Adding Binary Numbers. Ken Bigelow. Mon, 09232002 (http://www.playhookey.com/digital/adder.html)