The fact (mentioned in Florian Eisele's answer) that the endomorphism algebra must be commutative gives a further necessary condition for $\mathbb{C}_H\uparrow^G$ to be multiplicity free: $N_G(H)/H$ must be abelian. For $\mathbb{C} N_G(H)/H$ appears as a subalgebra of the endomorphism algebra, coming from those double cosets labelled by an element of the normalizer.
In the case when $G$ is the symmetric group $S_n$, the problem of which permutation characters are multiplicity-free is completely solved for $n \geq 66$ by work of Mark Wildon: http://arxiv.org/abs/0903.2864
