We investigate Monte Carlo simulation strategies for determining the effective (“depletion”) potential between a pair of hard spheres immersed in a dense sea of much smaller hard spheres. Two routes to the depletion potential are considered. The first is based on estimates of the insertion probability of one big sphere in the presence of the other; we describe and compare three such methods. The second route exploits collective (cluster) updating to sample the depletion potential as a function of the separation of the big particles; we describe two such methods. For both routes, we find that the sampling efficiency at high densities of small particles can be enhanced considerably by exploiting “geometrical shortcuts” that focus the computational effort on a subset of small particles. All the methods we describe are readily extendable to particles interacting via arbitrary potentials.