I recently have been focused purely on making procedurally generated game content. So far I have covered everything in my experiments from tile based procedural generation to binary space partitioning to cellular automata. Below I will cover my ideas and concepts and would love any feedback or other peoples ideas on procedurally generated content.

Tile based generation:
Make random rooms, check for overlapping, establish a center for each room, loop through and connect closest rooms by center using either vertical or horizontally started corridors and marking the turning point chosen by which will stay the furthest away from other rooms and turning points.

Binary Space Partitioning:
Split the map and split into A and B split into A1-A2 and B1-B2 and continue to split randomly vertical or horizontal until space is more than double for the alternative then select the more sensible split. Instead of pairing as I split I instead use a rule that rooms generated cannot leave more than half dead space with height or width therefore I can link using center of space.

Cellular automata:
Currently I use the traditional 50% on and off starting state. If Less than two open neighbors, it goes solid. Two or three open neighbors, it stays open. More than three open neighbors, it goes solid. If a solid cell has exactly three open neighbors, it becomes open. If a border it goes solid. creating a new map by marching squares from starting layout with rule system.

Cellular automata is the most exciting system for me because it can be used to create different and realistic looking "biomes" for surface worlds like desert, plains, lava ect with just a little adjustment. The hardest part of using this system is trying to make realistic looking caves that connect. The only way I have figured out how to make corridors using this system is marching the squares and whenever I touch a room not numbered having a contagious wave of room number designation flood fill every touchable square of that room. After everything is said and done I create a corridor from the closest tiles with different room numbers.
PGC caves are notoriously difficult to get right. One of the more interesting Roguebasin articles I read on the subject suggested having random rock density, so that when tunneling from one cavern to another to connect them you would tend to follow the path of least resistance. In that way the path would pick up a random feel.

Two things I would suggest looking at for PCG are the Voronoi tessellation and graph theory.

For those unfamiliar with it, Voronoi tessellation is where you divide up a space into a series of polygonal cells. Each cell has a single "center" point, and every point inside the cell is closer to that center point than to any other cell's center point. Or to put it a simpler way, imagine you're in a room with a bunch of other people; whatever space is closer to you than anyone else belongs to you. This kind of thing can produce very interesting, organic-looking maps. If the points are very random, the result may be very haphazard with some cells being very small, but you can "relax" the tessellation a few times by averaging the corners of each polygon to get a new center point for each cell; that tends to spread the points out more evenly.

Where graph theory comes into play is that in any kind of tessellation--tiles, hexagonal, Voronoi, whatever--you have cells with neighbors. You can think of each cell as a node in a graph, and wherever two nodes connect you have an edge. With graph theory you can map out articulation points--nodes that, if removed, would split the graph up into more than one piece--and bridges (the edge version of the same thing). You can use this knowledge to build complex puzzle chains, like for instance placing quest rewards behind locked doors.