Quantum magnetism originates from the exchange coupling between quantum mechanical spins. Here, we report on the observation of nearest-neighbor magnetic 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, which allows temperatures below the exchange energy for a subset of lattice bonds. When loading a repulsively interacting gas into either dimerized or anisotropic simple cubic configurations of a tunable-geometry lattice, we observe an excess of singlets as compared with triplets consisting of two opposite spins. For the anisotropic lattice, the transverse spin correlator reveals antiferromagnetic correlations along one spatial axis. Our work facilitates addressing open problems in quantum magnetism through the use of quantum simulation.