Monte Carlo sampling was initiated in the 40s by the likes of Ulam and Metropolis in Los Alamos, to study (atomic) physics problems. Since then, it has become a fantastic tool at the roots of statistical physics. A large part of the activity in this area is to develop better heuristics and to understand their properties.  We will present a review of partial results and open problems regarding sampling and estimation of the partition function from a physicist's point of view, with a focus on a very difficult problem called spin glasses. We will attempt to highlight the algorithms and methods used in practice, the problems for which better algorithms are needed, and the open problems for theoretical analysis.