Dynamical processes taking place on networks have received much attention in recent years, especially on various models of random graphs (including "small world" and "scale free" networks). They model a variety of phenomena, including the spread of information on the Internet; the outbreak of epidemics in a spatially structured population; and communication between randomly dispersed processors in an ad hoc wireless network. Typically, research has concentrated on the existence and size of a large connected component (representing, say, the size of the epidemic) in a percolation model, or uses differential equations to study the dynamics using a mean-field approximation in an infinite graph. Here we investigate the time taken for information to propagate from a single source through a finite network, as a function of the number of nodes and the network topology. We assume that time is discrete, and that nodes attempt to transmit to their neighbors in parallel, with a given probability of success. We solve this problem exactly for several specific topologies, and use a large-deviation theorem to derive general asymptotic bounds, which we use, for example, to show that a scale-free network has propagation time logarithmic in the number of nodes, and inversely proportional to the transmission probability.