Papers to credit for spectral partitioning of graphs
It seems that the first paper introducing this set of ideas (using the algebraic invariant $\lambda_2$, the second smallest eigenvalue of the graph Laplacian, to bound various properties of the graph) to graph theory was Fiedler's "Algebraic Connectivity of Graphs" in Czechoslovak Mathematical Journal. It appeared in 1973,  roughly at the same time as the Cheeger's paper (1970), which dealt with manifolds. I am not sure who was the first to observe the parallel between graphs and manifolds in that respect. $\lambda_2$ is sometimes called the Fiedler number. 

Interestingly, there is a remark at the end of the Fiedler's paper, pointing out an independent technical report by Anderson and Morley titled Eigenvalues of the Laplacian on a Graph from 1971, which apparently had similar ideas. However, it the paper by Anderson and Morley with the same title appeared in Linear and Multilinear Algebra only in 1985.