The topics of the title are intimately connected to each other, and to a host of other topics, in beautiful ways. It has been known since the time of Kirchhoff (1847) that one can solve electrical network problems by using various probabilities associated to choosing a spanning tree at random (uniformly) from a finite graph. Algorithms for generating a random spanning tree are connected to generation and counting of states in arbitrary Markov chains.
A ``thermodynamic'' limit defines the model on infinite graphs. Here, the connections to potential theory deepen and allow one to resolve many questions, such as the number of components and the topology of components. We will describe work on random spanning trees of Aldous, Benjamini, Broder, Burton, Kenyon, Kesten, Kirchhoff, Pemantle, Peres, Schramm, Wilson, and the speaker. Because of connections to other areas such as domino tilings, matroids, amenability, percolation, L^2-Betti numbers, Brownian motion, and conformal maps, there are still an enormous number of fascinating open questions.