Why is a push up harder to achieve on a mattress? Why is doing a push up harder on a spring platform, such as a mattress? It might be more to do with lateral movement and stability, its not that you do more work on the vertical movements but rather in stabilising yourself during the motion?
Edit:
Some answers have addressed the problem from different points of view, for example, Deschele Schilder has elaborated on the extra work involved in stabilising oneself. And user256872 has mentioned that extra work is actually done against the vertical forces because you are doing work against the spring and gravity. There are some points in the answer that I'm not grasping, specifically

To push yourself up, you're pushing on the trampoline, which will deform. Since it will sink, the trampoline and whatever's on it will get lowered. However, you're not trying to go lower, you're trying to go higher, so you need to push down even harder to accelerate upwards, which in turn pushes the trampoline lower..

This scenario seems balanced to me such that no displacement of the body would actually occur from the reference frame of the ground. I'd like to actually be able to show whether this is the case and whether more work is actually done mathematically. Consider the simplified scenarios shown in the image

In the first scenario, an object of mass $m$ is at rest on a spring, such that the spring is compressed by an amount $l=|\vec{F}_1|/k=mg/k$, where $k$ is the spring constant and $g$ the acceleration due to gravity. In the second, an additional force $\vec{F}_2=m\vec{g}+\vec{F}_P$, is applied (the push up), where $\vec{F}_P$ is the push up force, for a duration $\tau$ to the spring which compresses it further. The work done against the spring and gravity is then
$$\begin{align}\Delta W_s+\Delta W_g&=\frac{1}{2}k\left(l+\Delta l\right)^2-\frac{1}{2}kl^2+mg\Delta d\\&=\frac{F_P}{k}\left(mg+\frac{F_P}{2}\right)+mg\Delta d\end{align}$$
where $F_P=|\vec{F}_P|$, $g=|\vec{g}|$, $\Delta W_s$ is the work done against the spring, and $\Delta W_g$ the work done against gravity. From this, how can we show that the work done is greater than the stiff spring case i.e.
$$\Delta W_s+\Delta W_g>\left(\Delta W_s+\Delta W_g\right)\Big|_{k\rightarrow\infty}.$$
Obviously in this case $\Delta W_s\Big|_{k\rightarrow\infty}=0$, and $\Delta W_g\Big|_{k\rightarrow\infty}=mg\left(\Delta l+\Delta d\right)$. Subbing this into the above inequalty, we find that the work is always greater for
$$F_P>0.$$
Is this correct? However, this does not tell us anything about the $\Delta d$ contribution as it cancels.
 A: First, let's cover how a pushup is done on the floor. Your hand applies a force onto the floor, and the floor applies an equal and opposite force on you, which you use to push yourself up. The important part is that you push on the floor. However, the floor, being very rigid and massive, does not deform or move.
Next, let's consider a trampoline or a mattress (though a trampoline is more interesting, so I'll stick with that). To push yourself up, you're pushing on the trampoline, which will deform. Since it will sink, the trampoline -- and whatever's on it -- will get lowered. However, you're not trying to go lower, you're trying to go higher, so you'd need to push down even harder to accelerate upwards (which in turn pushes the trampoline even lower, which means you'd also have to accelerate much faster than normal). So not only must you push yourself over a longer distance (this also depends on how much you compress the trampoline, and how quickly you do your pushups), but you must apply a greater force.
The following is more true for a trampoline that springs up with great acceleration: as the trampoline is going up, your hands and feet are going up with it. However, if the trampoline accelerates fast enough, your hands and feet would need to generate a very large force to elevate the rest of your body. Imagine yourself lying down in an elevator that's accelerating upwards quickly --  you'll find it difficult to get up.
It should be noted that push-ups on a trampoline are not necessarily harder; you could utilize the trampoline to cheat to your advantage, since, after all, it is a trampoline. You could throw your body down, such that the force you apply on the trampoline is much bigger than your weight. Then, once it sinks and starts to rise, the trampoline would accelerate you upwards, in which case you shift your body up while applying little force with your hands. This is pretty much how people jump on trampolines (except you're attempting push-ups). Of course, that is a rather pointless "workout," although an interesting example of resonance.
In short, there are several variables, namely your position, push-up speed and frequency (resonance), and push-up location (i.e. when the trampoline is peaked vs. lowered) that would allow you to change the work necessary -- for easier or harder pushups.
A: A spring mattress on your bed (which can have a spring underground too) wobbles and vibrates when you do push-ups on it. You have to correct for all these extra induced motions. Extra energy is needed to keep yourself balanced.
On average, your body stays at the same height (as it would on solid ground) but more energy is required to keep yourself steady.
You can do your push-ups very slowly. This will reduce the induced mattress motions. However, the slightest imbalance will induce motion, so you will need extra energy too to keep your body shaped in a way to induce fewer motions.
So no matter how you perform the push-ups, more energy is needed and it will be more difficult to keep your body in balance.
So on top of the work done in the vertical direction, you have to perform work in the horizontal direction to keep your body in the same position upon each return. You can do this by moving your arms or your body horizontally. That is you have to do work to keep your balance. Not knowing exactly how the mattress will react to your movements in advance will make it much harder too (if you mean by harder more difficult instead of using more energy).
To address your question a bit extra (after the edit you made): if you would do push-ups on a mattress in which the springs could only move vertically, you could induce motions of the mattress that could make the mattress "resonate" if you push-up with the right frequency. This would be a nice push-up! Maybe you could reach the ceiling... The motion of the mattress is sent back to you, due to the springs pushing back. To counteract this "returned momentum" you have to counteract also in a vertical direction because else you could find yourself in a resonance state, which is not what you want, I guess. You could reduce this vertical motion by doing the push-up with a frequency that's slow compared to the resonance frequency (in which case the springs stay compressed, more or less). If you do it fast as compared to this frequency, only your arms will move, as you can imagine. It remains to be seen if you need less energy for this because your body will not move up and down that much, but you have to compress the springs on every push-up. I'll leave that to others.
