Quantum discord, a measure of genuinely quantum correlations, is generalized to continuous variable systems. For all two-mode Gaussian states, we calculate analytically the quantum discord and a related measure of classical correlations, solving an optimization over all Gaussian measurements. Almost all two-mode Gaussian states are shown to have quantum correlations, while for separable states, the discord is smaller than unity. For a given amount of entanglement, it admits tight upper and lower bounds. Via a duality between entanglement and classical correlations, we derive a closed formula for the Gaussian entanglement of formation of a family of three-mode Gaussian states.