A random walk on an infinite graph is recurrent iff ...?

This is a huge subject, but the best introductory reference remains:

Doyle, Peter G.; Snell, J.Laurie, Random walks and electric networks, The Carus Mathematical Monographs, 22. Washington, D. C.: The Mathematical Association of America. Distr. by John Wiley & Sons, New York etc. XIII, 159 p. £ 22.00 (1984). ZBL0583.60065.

They present quite a few tools to answer the question.

In my opinion, the closest to a "master theorem" is the criterion due to Terry Lyons, according to which a reversible Markov chain on a countable state space (in particular, the simple random walk on a locally finite graph) is transient if and only if there exists a flow of finite energy on the state space.

PS Contrary to the opinion appearing in the comments, in this criterion no conditions other than reversibility (e.g., uniform bounds on vertex degrees) are imposed. Actually, there are quite instructive examples of reversible random walks with unbounded weights (for instance, any nearest neighbour random walk on a tree).

---

   
    ^{Theorem from Terry Lyons paper (added by J.O'Rourke).}

---