Both
Die Schuhe sind unter dem Bett.
and
Die Schuhe stehen unter dem Bett.
are correct. There's a slight difference in meaning, though. With
Die Schuhe sind unter dem Bett.
you just express that the shoes are, well, under the bed ;) With
Die Schuhe stehen unter dem Bett.
you give the impression that the shoes are standing upright (and not laying on the side, for example), probably neatly one next to the other.
As a rule of thumb, the variation with "stehen" is probably used more commonly, but as I said, both are basically correct.
As for why, it's generally hard to say why a community of speakers decided to express something one way or the other. Why do many (western) languages use the verb "to be" as the copula (as in "The sky is blue"). Why do several languages use the verb "to go" to express whether somebody is well ("Wie geht es Dir?", "How is it going?", "Comment ça va ?" in French and so forth). Why do Japanese speakers often omit the subject, and why is the copula often ommited in Russian or Ukranian? To all those questions the answer is, we don't really know ;)
"Aufliegen", by the way, refers to something lying flatly on top of something else, probably with its whole surface. If you say
Die Zeitung liegt auf dem Bett auf.
you express that the newspaper is laying flatly on the bed, probably not folded or crumpled or something. In most cases, just
Die Zeitung liegt auf dem Bett.
would be perfectly fine and enough.