Exact solutions of Gaussian solitons in nonlinear media with a Gaussian nonlocal response are obtained. Using the variational approach, we obtain the approximate solutions of such solitons when the degree of the nonlocality is arbitrary. Specifically, we study the conditions for Gaussian solitons that propagate in weakly and highly nonlocal media. We also compare the variational result with the known exact solutions for weakly and highly nonlocal media.