No experiment to date provided evidence for quantum features of the gravitational interaction. Recently proposed tests suggest looking for the generation of quantum entanglement between massive objects as a possible route towards the observation of such features. Motivated by advances in optical cooling of mirrors, here we provide systematic study of entanglement between two masses that are coupled gravitationally. We first consider the masses trapped at all times in harmonic potentials (optomechanics) and then masses released from the traps. This leads to the estimate of the experimental parameters required for the observation of gravitationally-induced entanglement. The optomechanical setup demands LIGO-like mirrors and squeezing or long coherence times, but the released masses can be light and accumulate detectable entanglement in a timescale shorter than their decoherence times. No macroscopic quantum superposition develops during the evolution. We discuss the implications from such thought experiments regarding the nature of the gravitational coupling.