Procedural generation is the act of creating game content just before or during a new game session. This is mostly used in regard to game levels: from the placement of enemies on the map to a creation of a whole game world. Many games use procedural techniques, from Minecraft and Roguelikes to No Man's Sky and even simple games such as Flappy Bird.
The strengths of procedural generation include reduced application size, increased content and variety as well as added repetition value. These concepts power the skirmish mode in Sid Meier's Civilization, Age of Empires and many others.
A good generator can easily add additional free content as opposed to human crafted levels which may require a great amount of time and effort to make. An extremely powerful yet sometimes overlooked quality of such generators is determinism.
Procedural determinism is the ability to recreate a set of data every time. This is done by using deterministic random number generators and supplying the same seed or key which resulted in the desired data. Take Minecraft for example: when starting a new game you have an option to enter a seed, use the same seed every time and you will have the same world. A good example can be seen at Amit Patel's polygonal island generator demo.
Recreation of data is good for more than being able to share exciting worlds you stumbled upon with your friends. Banished's developer created an island generator and found a map he liked so he based his tutorial around its seed. Building a multiplayer game and don't want to send a whole lot of data? Share the seed and let both clients create the same world and only share changes which happened during the game.
Lately I have been experimenting with some game concepts, going from strategy to turn-based roleplaying and a hero-civilization hybrid. I found procedural generations extremely helpful to test ideas quickly; from generating islands for a game similar to The Settlers or dungeons and caves for an RPG, creating a simple generator is a task that should only take a few hours to a day or two thanks to all the information available on the web and allows to get a feel for the game and make it interesting quickly.
Another use for determinism is in game analytics. If you are creating a game like Flappy Bird [for the sake of simple example] and want to see all the deaths of a certain player you only need to send the seed for the session, the length of the session in seconds and the Y position of the player when he died. You can then easily find the position of player when they died by recreating the level with the seed and simulating the change over time and positioning the player with the delta time and Y position.
This can be easily extended for more complex game such as RPGs and Strategies. Depending on the amount of the data you send you can create replays for every game and world created.
Some resources I have found extremely useful when building my own level generators: