I think the basic point of contact between graph theory and linear algebra is the notion of a random walk. Given an initial probability distribution $p$ on the vertex set $V$ of a graph (though of as a vector in $\mathbb{R}^{|V|}$), the probabilities of hitting different vertices after $k$ steps of a random walk are given by $W^k p$ where $W = A D^{-1}$ (with $A$ the adjacency matrix and $D$ the degree matrix). This suggests that the spectral theory of $W$ is going to be relevant to dynamical questions on graphs, and the (normalized) Laplacian is just $D^{-1/2}(I - W)D^{1/2}$. (The point of the normalization is so that eigenvalues for different graphs can be compared).
You ask specifically why spectral theory for the Laplacian helps measure the connectivity of a graph. Let's first note that it is possible to use random walks to answer this question. Suppose a graph is very loosely connected, meaning it can be divided into two pieces which each have many internal connections but very few external connections. Pick any vertex and start doing random walks of various lengths starting at that vertex. Intuitively, you expect that these random walks will be much more likely to visit vertices in the same piece as the starting vertex and much less likely to visit vertices in the other piece, and this intuition can be made precise.
Of course you will still probably see vertices with high degree more often then you will see vertices with low degree, so you should compare the random walk probabilities to the degree vector of the graph (normalized so that it is a probability distribution). The normalized degree vector is an eigenvector for $W$ with eigenvalue $1$, so it is not unreasonable to expect that the small eigenvalues of the Laplacian (which is conjugate to $I - W$) will carry similar information.
A question you might ask is: why use the Laplacian at all if the intuition comes from random walks? The first answer is historical: the theorem relating the connectivity of graphs to the spectral theory of the Laplacian began as the Cheeger inequality, a theorem relating connectivity of Riemannian manifolds to the spectral theory of the Riemannian Laplacian operator (the two theorems have nearly identical proofs). A more substantive answer is that for any vector $f \in \mathbb{R}^{|V|}$ we have:
$$\langle Lf, f \rangle = \sum_{u \sim v} (f(u) - f(v))^2$$
which is a particularly simple quadratic form on the graph, and thus linear algebra and spectral theory for $L$ is quite simple (and the estimates are pretty sharp).
Best Answer
Some other examples are the Erdos-Moser conjecture (see R. Proctor, Solution of two difficult problems with linear algebra, Amer. Math. Monthly 89 (1992), 721-734), a few results at http://math.mit.edu/~rstan/312/linalg.pdf, and Lovasz's famous result on the Shannon capacity of a 5-cycle and other graphs (IEEE Trans. Inform. Theory 25 (1979), 1-7). For a preliminary manuscript of Babai and Frankl on this subject (Linear Algebra Methods in Combinatorics), see http://people.cs.uchicago.edu/~laci/CLASS/HANDOUTS-COMB/BaFrNew.pdf .