That's it! That's the difference. I could not think of how to explain it. You're welcome. This is why this sentence sounds so odd to me. When you use «em», it is usually resting "on" something: «em cima da mesa» = "on top of the table." When you use «por», it does not necessarily have to be "on" something: «A mosca voa por cima da mesa.» = "The fly flies above the table." This is why this sentence seems a bit weird to me; the cat is not stuck to the underside of the bed while it is sleeping (unless it is a low bed), so I would much prefer to say «por baixo» here. Admittedly, though, I do not often use «embaixo».
I wonder if it's regional. I spend nearly all my time in the northeast and most of my Brazilian friends are from there and I only ever see/hear abaixo in colloquial language. Pernambuco does have a lot of linguistic idiosyncrasies. I've learned that things I learn there do not necessarily apply to the rest of the country, haha.
No, it does not translate to that. You need the «de» (which contracts to «da» since «cama» uses the feminine article) for the same reason that you need the "of" in English when you say "on top of the bed;" you just cannot say "on top the bed" (at least , not in formal English), and you cannot ever say «embaixo a cama».