We prove the Li-Yau gradient estimate for the heat kernel on graphs. The only assumption is a variant of the curvature-dimension inequality, which is purely local, and can be considered as a new notion of curvature for graphs. We also derive Harnack inequalities and heat kernel bounds from the gradient estimate, and show how it can be used to strengthen the classical Buser inequality relating the spectral gap and the Cheeger constant of a graph