What is the most carbon-efficient way to take off in a passenger plane?
You are right, climbing adds to the fuel consumed, and increases the energy which is added to the plane, but this energy is conserved and can be reclaimed later, on descent. There are two kinds of energy to consider, potential and kinetic energy. Potential energy is weight times height, and kinetic energy is mass times speed squared, and both can be interchanged.
$$E = \frac{m}{2}\cdot v^2 + m \cdot g \cdot h$$
Nomenclature:
    $E \:\:\:$ energy
    $m \:\:\:$ mass
    $v \:\:\:\:$ speed
    $g \:\:\:\:$ gravitational constant
    $h \:\:\:\:$ height

The thrust of the engines over what is needed to overcome drag, accumulated over time, builds up energy. Lift and Drag, in turn, are proportional to airspeed squared times density of air, so if the airplane climbs, it needs to fly faster to compensate for the thinner air, and drag will stay roughly constant. Thrust is also proportional to the density of the air around the aircraft, and the same goes for fuel consumption. This means that the aircraft will approximately consume the same amount of fuel over time when it flies low and slow, and when it flies high and fast. Since the task is to transport people or goods to a specific destination, flying high and fast will result in less running time at the same fuel flow. This is the reason why flying high results in less CO2 produced!

When the aircraft comes close to its destination, it can now put the potential energy which has been stored as altitude to good use: In a descent, the thrust generation can be reduced by the amount of energy which is now reclaimed, just as you can ease off the gas pedal in your car when coasting downhill. So for the last half hour of the flight, the aircraft will now consume less fuel than before, and by the time it has reached its destination, the difference is just as big as the excess in consumption which was needed during climb.

For the nitpickers: The aircraft will weigh less at the end of the trip (fuel has been consumed), so the descent will not completely compensate for the climb. On the other hand, the lower temperature at altitude will reduce fuel consumption by letting the engines run more efficiently, so in the big picture a definite gain remains.