Oh gosh, this is such a tricky question.
The face-value answer is: They'd need to be the same number of megapixels as your own camera (I assume you're combining them with some of your own photos?) so that their quality is a good match, if you know what I mean.
However, it isn't always so. If you're using a stock image for a background, well, backgrounds tend to be blurrier than a subject, so you might get away with a smaller file. In fact, sometimes I've successfully used very small phone photos as backgrounds (artistically blurred, of course) for composites.
I guess what I'm trying to say is, get them as close in size to your own photos as possible. If you can't get them that big, pay very close attention to how you use them, to make sure your composite doesn't end up with glaring disparities of focus.