I had actually been looking into doing procedural generation of TMX maps for a 2d side-scroller, so that essentially all that would need to stored for each map would be the seed values. Unfortunately I only got a javascript / canvas prototype working for testing what the maps would look like - I hadn't gotten a chance to port it to objective-c. However the general idea would be the same.
The approach I used ( which is only one possible of many ) was to use seeded perlin noise generation, then use pixels from the generated image as a height map. There is also recursive sub-division that can generally yield decent results, but my experiments seemed to indicate that it didn't work as well for a side-scrolling platformer ( with multiple levels ala Maple Story ) as it did for top-down or 3d terrain. A noise generation algorithm like perlin would likely give good results for something like Tiny Wings ( from what I saw in the screenshots ). Recursive subdivision could potentially work well too.
Regardless of the approach you take for generation, they key behind all of it is using a seeded random number generator. This will give consistent results for the numbers from a given seed every time.
You can also use procedural generation for textures and the like ( check out the .kkrieger demo for an absolute killer demo of what's possible ). For getting specific textures like known materials there is a good bit more trial and error and there are tools to assist you. For textures like you see on Tiny Wings, you could simply use the numbers from your PRNG to feed mathematical functions, then assign colors. You could even take simpler approaches - the main limit is really your imagination.
Based off the type of game-play it seems Tiny Wings has, I would guess that they're using a physics engine to drive terrain and interactions. This could be approached in a similar manner to the canabalt-style endless runner games, where you use the generated values to create bodies for the ground and just roll with it from there.
I'm sorry I don't have the objective-c code to post for you, but hopefully this should get you going in the right direction. =)
Here's a screenshot as a sample - it's not the same style, but should give you an idea of what's possible.
