We establish a generic method to analyze the time evolution of open quantum many-body systems. Our approach is based on a variational integration of the quantum master equation describing the dynamics and naturally connects to a variational principle for its nonequilibrium steady state. We successfully apply our variational method to study dissipative Rydberg gases, finding very good quantitative agreement with small-scale simulations of the full quantum master equation. We observe that correlations related to non-Markovian behavior play a significant role during the relaxation dynamics towards the steady state. We further quantify this non-Markovianity and find it to be closely connected to an information-theoretical measure of quantum and classical correlations. © 2016 American Physical Society.