I think exactly how your game is designed would affect how exactly you would go about it. Like what the pieces were like, whether the layout was tile-based, etc. I can think of an idea where the game is tiled and everything takes up one "square," then you could just have the game spawn a new set of squares for a column once the player has reached a certain relative column. If you want the game to auto-scroll so the player doesn't control the horizontal movement of the game field, you could just have it constantly "pushing" the grid to the side and spawning new columns as it goes. It would have to check to make sure there was enough "free space" to let the player get through, and if you wanted to make sure multiple paths were available, this would take more checking.
You could also make it a little more pseudo-random landscapes by creating pre-made "screens" where you create entire screen-sized maps yourself with pre-placed platforms, then give each a property of which ones it can connect to on each side, then have the game "link" those screens together as the player moves. If you've ever seen Mega Man 9 or 10 Endless Attack mode, it is something like that... the maps are already laid out, but the order you encounter them is random. While MM9/MM10 use entire stretches of premade maps, you could make them just small screens and have them link together in a random order.
"Run until you die" games often have what I think you're looking for, and they usually use the second example (because they often get very fast, and the player can "learn" what to expect, so it's not 100% random placement of the objects). Play games like Doodle Jump, Gravity Guy, and Jetpack Joyride and you will get kind of an idea of how this kind of concept is put into play. Then adapt that to the kind of game you're wanting to make.
I would also go ahead and plan all of the types of "pieces" you would like to use, and create a couple non-random stages for a player to play (playable or even just in concept). Then you will have an idea of how exactly all your pieces fit together, and what requirements they have for joining each other. Once you know all the kinds of pieces you want exactly, you will have a better idea of how you should go about randomly fitting them together.
In the end, there are many ways you could do this (once I made a game like this in an old game creation software, where off the screen there was an object flying around and it would "fire" out platforms at random intervals like a gun lol... this is probably not the best idea though) and the way you end up doing it will depend a lot on how you design your pieces, how fast-paced you want the game to be, what kind of control the player will have over the direction of the screen, etc. Create the entire game in planning, and the path to how you should create this one element of it should open up.