Vayikra 26:1 says:
You shall not make idols for yourselves, nor shall you set up a statue or a monument for yourselves. And in your land you shall not place a pavement stone on which to prostrate yourselves, for I am the Lord, your God.
This teaches us (See Chinuch, Mitvah 349) that one is not allowed to prostrate oneself on stone outside the Beit HaMikdash (since it says "in your land"). The Rabbis extended this prohibition to even forbid bowing on one's knees (without prostrating oneself) on stone.
The Rambam says that this is because this was the way non-Jews would worship their gods. They would place decorated stones before their gods and use them to bow to their gods.
The Chinuch (I think) adds that it is possible that it may appear that one is worshiping the stone itself, since it is set aside and decorated, etc. However, the Chinuch says, if one were to prostrate oneself on a carpet (even a nice one), we aren't worried that one will turn it into a god, since it will (relative to the rock) quickly wear out.
Rashi (Megilla 22B) indicates that the issue is not to bow the way they bowed in the Beit Hamikdash (it appears that he hold it is forbidden to build a Beit HaKnesset with a stone floor - I'm not sure if that's right)
Halachically Speaking Volume 5, Issue 14 discusses this at length, and says "All sources say a separation is required between ones face and the ground not a separation between the knees and the ground." but continues "Some say falling on one’s knees alone is going in the ways of the non-Jews and one
should avoid this.". According to that perhaps one should put something between his face and knees as well.
Chabad custom is not to worry about this if the floor is made out of wood.