Why do gerbes live in H^2? Line bundles on a scheme $X$ live in $H^1(X,O_X^*)$, where $O_{X}^{*}$  is the sheaf of invertible functions. If $X$ is noetherian separated, then we can think of this $H^1$ to be Čech cohmology w.r.t. an open affine cover of $X$. We can think of a line bundle as a principal $\mathbb{G}_{m}$ -bundle,  where $\mathbb{G}_{m}$  is the multiplicative group scheme, i.e. the result of patching together, via $\mathbb{G}_{m}$ -valued transition functions, local pieces that look like $ U \times \mathbb{G}_{m} $ for $U$ open in $X$.
I apologize if the question sounds trivial to people who have a serious knowledge of stack theory. 
First of all, let's take the following definition of "gerbe" (can find in Wikipedia): a gerbe on $X$ is a stack $G$ of groupoids over $X$ which is locally non-empty (each point in $X$ has an open neighbourhood $U$ over which the section category $G(U)$ of the gerbe is not empty) and transitive (for any two objects $a$ and $b$ of $G(U)$ for any open set $U$, there is an open set $V$ inside $U$ such that the restrictions of $a$ and $b$ to $V$ are connected by at least one morphism). And in this context, I think we should add that, locally over $X$, $G$ should be isomorphic to $U\times B \mathbb{G}_{m}$ ($B \mathbb{G}_{m}$ is the classifying stack of $\mathbb{G}_{m}$).
I was told that $\mathbb{G}_{m}$ -gerbes over $X$ up to equivalence correspond to cohomology classes in $H^2(X,\mathbb{G} _{m})$. 
I would like to understand in concrete (Čech) terms why this bijection should take place. In other words: why the process of patching classifying spaces (edit: rather, classifying stacks) of a group involves passing to the second cohomology group? 
 A: I have a couple things to say.
First, believe your definition of gerbe is slightly incorrect. When you say that your stack is locally isomorphic to $U \times B\mathbb{G}_m$, this isomorphism needs to preserve some additional structure. It might be okay for $\mathbb{G}_m$-gerbes, by accident, but for general non-abelian gerbes you will run into trouble. (It might still be okay for $\mu$-gerbes, where $\mu$ is a sheaf of abelian groups over X).
There are several ways to add this extra structure, but I think the most common are not necessarily the most enlightening. The fact of the matter is that $B\mathbb{G}_m$ is a group object in stacks and it "acts" on the gerbe over $X$. The local isomorphism to $U \times B\mathbb{G}_m$ needs to respect this action. Morally, you should think of a gerbe as a principal bundle with structure "group" $B\mathbb{G}_m$. 
The reason that this isn't the most common way to explain what a gerbe is, is that making this precise requires a certain comfortability with 2-categories and coherence equations that most people don't seem to have. Times are changing though. Just as for ordinary principal bundles, you can (in nice settings, say noetherian separated) classify them in terms of Cech data. When you do this you see that the only important part is the coherence data, which gives a 2-cocycle. For non-abelian gerbes you get non-trivial stuff which mixes together parts which look like data for a 1-cocycle and a 2-cocycle. I agree with Kevin that, at this point, if you really want to understand this stuff you should fill-in the rest of the details on your own. It is a good exercise!
Alternatively, if higher categories make you uncomfortable, you can be cleaver. You can still make a definition along the lines of the one you outline precise without venturing into the world of higher categories and "coherent group objects in stacks". I recommend Anton's course notes on Stacks as taught by Martin Olsson. Section 31 has a definition of $\mu$-gerbes which is equivalent to the one I sketched above but avoids the higher categorical aspects. There is also a proof that such gerbes are classified by $H^2(X; \mu)$. Enjoy!

Just to reiterate. In a gerbe you are not patching together classifying spaces, you are patching together classifying stacks. Despite the common notation, there is a difference. A stack is fundamentally an object in a 2-category. This means that you need to deal with 2-morphisms and that they can be just as important as the 1-morphisms. For $B\mathbb{G}_m$, the 1-morphisms (which preserve the multiplication 
action of the stack $B \mathbb{G}_m$ !!) are all equivalent, so there is no Cech 1-cocycle data at all. All you get are the coherence data, which form a 2-cocycle. 
This is one reason that I prefer the notation $[pt/\mathbb{G}_m]$ to denote the stack $B\mathbb{G}_m$. This is particularly important in the topological setting where these are truly different objects. 
A: A nice point of view is to consider principal bundles with structure group $B\mathbb{C}^\times$. One can probably take any abelian Lie group instead of $\mathbb{C}^\times$. Principal $B\mathbb{C}^\times$-bundles are one way to give a precise meaning to what you are calling "patching together classifying spaces". 
The point is that there is an isomorphism
$$
H^1(X,B\mathbb{C}^\times) = H^2(X,\mathbb{C}^\times),
$$
which explains the relation to the second cohomology group. It is basically saying that principal $B\mathbb{C}^\times$-bundles are the same as $\mathbb{C}^\times$-gerbes. 
This isomorphism is induced from the exact sequence
$$
1 \to \mathbb{C}^\times \to E\mathbb{C}^\times \to B\mathbb{C}^\times \to 1
$$
of groups, and the fact that the sheaf of $E\mathbb{C}^\times$-valued functions on a paracompact space $X$ is soft. All this is very nicely explained in Gajer's Inventiones paper "Geometry of Deligne cohomology". 
