The exchange coupling between quantum mechanical spins lies at the origin of quantum magnetism. We report on the observation of nearest-neighbor magnetic spin correlations emerging in the many-body state of a thermalized Fermi gas in an optical lattice. The key to obtaining short-range magnetic order is a local redistribution of entropy within the lattice structure. This is achieved in a tunable-geometry optical lattice, which also enables the detection of the magnetic correlations. We load a low-temperature two-component Fermi gas with repulsive interactions into either a dimerized or an anisotropic simple cubic lattice. For both systems the correlations manifest as an excess number of singlets as compared to triplets consisting of two atoms with opposite spins. For the anisotropic lattice, we determine the transverse spin correlator from the singlet-triplet imbalance and observe antiferromagnetic correlations along one spatial axis. Our work paves the way for addressing open problems in quantum magnetism using ultracold fermions in optical lattices as quantum simulators.