The Vlasov-Poisson system is an important nonlinear transport equation, used to describe the evolution of particles under their self-consistent electric or gravitational field. The existence of classical solutions is limited to dimensions d <= 3 under strong assumptions on the initial data, whereas weak solutions are known to exist under milder conditions. However, in the setting of weak solutions it is unclear whether the Eulerian description provided by the equation physically corresponds to a Lagrangian evolution of the particles. In this article we develop several general tools concerning the Lagrangian structure of transport equations with nonsmooth vector fields, and we apply these results to show that weak/renormalized solutions of Vlasov-Poisson are Lagrangian and actually that the concepts of renormalized and Lagrangian solutions are equivalent. As a corollary, we prove that finite-energy solutions in dimension d <= 4 are transported by a global flow (in particular, they preserve all the natural Casimir invariants), and we obtain the global existence of weak solutions in any dimension under minimal assumptions on the initial data.