It seems that the first answer should be "every time it gets stained." But the truth is that, although the cover will get stained often, we would have to replace it very often if we decided to wash it every single time. It is recommended to change it at least once a week.
We must also keep in mind that the changing table can become the ideal environment for bacteria if it is not kept properly clean. Therefore, using the same cover for more than a week without cleaning can be harmful for the babies skin.