Randomly generated dungeons are usually constructed of a number of distinct setpieces shuffled in a variety of positions. The method of randomizing varies from game to game, of course, but all maintain some level of consistency from one version of the dungeon to another.
All have an entrance and/or exit, of course, and whatever triggers or unique areas are required for certain quests or monsters. These might include spawn points or teleporters or a unique room that stays consistent each time you play (for example, The Butcher in Diablo is always found in the same square room every time you reach the second level).
While the concept of randomizing a dungeon gives the sense of replayability, it can often be a double-edged sword as many randomized dungeons feel overly artificial and dull. If the process is not well constructed, a randomized dungeon can be overly confusing, require a lot of backtracking, and can harm the player's experience. Keeping the dungeons feeling moderately unique while not alienating the player is a challenge that few developers have met.
Diablo II is one of the more popular games that features randomly generated dungeons. It also doesn't rely wholly on the feature - many of the important areas are not randomly generated or feature fixed rooms for quest items or bosses. As an example, the magician's realm in the second act has four sides with randomly determined paths, and the boss is not located in a fixed direction from your starting point. His platform, however, is identical no matter what side of the level he's located on, as is the cluster of enemies surrounding him.
Most of the random generation in Diablo II is of little consequence outside of finding key points in each area - the waypoint (if any), sub-dungeon entrances, and the exit to the next area. Placement of lakes, trees, barrels, chests, enemies does not change the underlying game and occasionally that variation seems contrived.
All the dungeons in this old ACSII-based RPG are randomly generated, although unlike Diablo II or any other more recent game that uses the feature, Rogue was not programmed that way to add variety - it was almost a necessity given hardware and memory restrictions of the time.
While the main areas in Persona 3 are fixed, the dungeons of Tartarus are randomly generated, and in comparison to the previous two examples, Tartarus makes a good example of how not to use random generation. Random dungeons can fall into the trap of all looking the same - despite its graphics, the levels of Tartarus have little to distinguish themselves from Rogue's dungeons in terms of design. They simply look random, and blend into one another despite the existence of the occasional palette swap. Unfortunately, the game's placement of enemies does not help either, as they are not distinct from one another and simply show up as the same dark blob over and over again.