They arrive in the same relative position to the surface that they left. The teleportation device / spell does not distinguish between up / down / left /right --> it only disinguishes relative position to surface. So, in the Trek example, if you transport to a planet "below" you or "above" you, you stil end up on your feet; but, if you are lying down when transported, you are still lying down when you arrive. This was true in all cases I remember (such as the mountain climber).
I think that given RAW requires you to end up on a surface capable of supporting you and nowhere does it say it allows you to change position, the only logical conclusion is this. Otherwise, if you can end up in any position you want, I believe abuses could be conceived. Therefore, prone is still prone.