Using large scale QMC simulations, we investigate the ground state properties of interacting spins on the geometrically frustrated Shastry-Sutherland lattice. The spin system is described by an extension of the standard Shastry-Sutherland model to include exchange anisotropy and additional next-nearest neighbor interactions, J₃, on the "empty" plaquettes. Such generalizations have been shown to be necessary to explain the magnetic properties of the rare-earth tetraboride family of quantum magnets. For sufficiently strong J3, the ground state - in the absence of any external magnetic field - develops columnar antiferromagnetic order, similar to that observed in ErB4. Magnetization plateaus appear in a magnetic field. But more importantly, over a finite range of applied field, the ground state has simultaneous (columnar) diagonal and off-diagonal long range spin order - in other words, the ground state is a spin supersolid. We explore the parameter regime over which such a phase is stabilized, and discuss its relevance to real quantum magnets.