@Iglarion: Kartoffel is right, it's pretty much the oldschool approach that we use, no special shaders involved. The key is to divide the background into several layers. For Rigid Force Alpha I mostly try to seperate my scenes into foreground, midground and background layers. I make sure that there's a certain space between all these layers. This way you get a nice parallax scrolling effect. And furthermore, when you activate distance fog and simply play around with color and distance, you almost automatically get nice results.

The last screen you posted almost has the right direction. I assume that the high sand dunes assets in the background are 2D images. I'd move them further away from the camera to create more depths. Then I'd create some mid-poly sand dunes for the midground and some more detailed ones for the foreground, closest to the walkable area. I think that's pretty much the approach that Frozenbyte used for Trine 2: Trine 2 Desert. You should also take a look at other recent sidescrollers like Donkey Kong Country Returns, they all do it in a pretty similar fashion.

Also throw in a bunch of effects like sanddrifts or tumbleweeds passing by for that level and you're good to go!