We use the variational method to investigate the ground state phase diagram of the Kondo lattice Hamiltonian for arbitrary J/W, and conduction electron concentration n(c) (J is the Kondo coupling and W the bandwidth). We are particularly interested in the question under which circumstances the globally singlet (collective Kondo) Fermi liquid type ground state becomes unstable against magnetic ordering. For the collective Kondo singlet we use the lattice generalization of Yosida's wavefunction which implies the existence of a large Fermi volume, in accordance with Luttinger's theorem. Using the Gutzwiller approximation, we derive closed-form results for the ground state energy at arbitrary J/W and n(c), and for the Kondo gap at n(c) = 1. We introduce simple trial states to describe ferromagnetic, antiferromagnetic, and spiral ordering in the small-J (RKKY) regime, and Nagaoka type ferromagnetism at large J/W. We study three particular cases: a band with a constant density of states, and the (tight binding) linear chain, and square lattice periodic Kondo models. We find that the lattice enhancement of the Kondo effect, which is described in our theory of the Fermi liquid state, pushes the RKKY-to-nonmagnetic phase boundary to much smaller values of J/W than it was previously thought. In our study of the square lattice case, we also find a region of itinerant, Nagaoka-type ferromagnetism at large J/W for n(c) less-than-or-equal-to 1/3.