You essentially want to experiment with various noise functions, such as Perlin Noise. The various parameters you choose, and how you interpolate the information, will give you vastly different results.
As for how you transform the information into graphics, it'll vary. In Tiny Wings, there's clearly a foreground image that's 'cutout' above the noise function. Additionally a line gets drawn along the function to give the appearance of a border. In Dino Run, since the style is so simple, it's essentially filling the area below the function with a solid colour. Then sprinkle other stuff like trees and rocks around the level with some other noise function.
I don't have experience with Sprite Kit, so I wouldn't know if implementing it that way would be practical; I'd personally write a custom shader to draw it, using OpenGL ES.