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+a2S2(c2)] : It deviates from a Maxwell-Boltzmann f{MB} by a second order Sonine polynomial S2(c2) with a single adjustable parameter a2. We find a2 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, variant exp(-A x c{3/2}) . To our knowledge, this is the first time that Sonine deviations have been measured in an experimental system.