I've recently started to read up on how to randomly create levels and I'm certainly intrigued by the topic. Please be aware, that I'm in no way an expert on this matter, so expect this post to be mostly opinion based.
So far I have found two major factors making this concept a considerable problem. Firstly, you obviously want your player to be able to finish your level. It would be no good if you're supposed to open a door with a key, which is unfortunatly placed behind said door and therefore unreachable. Secondly, you want to ensure that your level isn't completely stuffed or looking abandoned and empty. The generator should also produce level designs, which are consistent with the mechanics, asthetics and flair of your game.
There are quite a few solutions for solving the problem of making a level playable from start to finish. In a blog post by the creator of Jack Benoit, he explains how he generated a level based on perlin noise and filled it with a guaranteed path for the player to find. The path had to satisfy a set of constraints, e.g. the height the player can jump.
If you take this principle and combine it with techniques used in artificial intelligence, namely constraint programming you end up with a very powerful tool, to describe your level generator. There is a paper from 2012 describing an application of said techniques.
I stumbled upon a very interesting approach to ensure a certain 'feeling' for your generated levels. It is called a rhythm based algorithm. With it you can model a certain rhythm in which the player traverses through your level. As far as I understand, you basically model or generate a movement rhythm, consisting of different states like waiting, moving, and jumping. This is then fed into a geometry generator, which in turn calculates a level layout with things like springs, placed according to the 'feel' represented by the movement rhythm.
Another interesting approach is also inspired by rhythm. You generate a start and end platform and let the solver choose a set of patterns, constricted by the physical capabilities of the player's character using a simple hill-climbing algorithm. If you happen to be interested in hill-climbing, or artificial intelligence for that matter, I would recommend checking out the video by computerphile about the basics of this algorithm, as well as some information about artificial intelligence in general.
There is a great paper doing a comparision of different generation algorithms, which also refers to some of the approaches mentioned in this post.
Well I hope you'll enjoy reading the linked material as much as I did. I may update this if I come across more awesomeness which is procedural level generation.