We present experimental results on the velocity statistics of a granular fluid with an effective stochastic thermostat, in a quasi-two-dimensional configuration. We find the base state, as measured by the single particle velocity distribution P(c) in the central high-probability regions, to be well described by P(c)=f(MB)[1+a(2)S(2)(c(2))]: It deviates from a Maxwell-Boltzmann f(MB) by a second order Sonine polynomial S-2(c(2)) with a single adjustable parameter a(2). We find a(2) to be a function of the filling fraction and independent of the driving over a wide range of frequencies and accelerations. Moreover, there is a consistent overpopulation in the distribution's tails, which scale as P proportional to exp(-Axc(3/2)). To our knowledge, this is the first time that Sonine deviations have been measured in an experimental system.