I first built the Random Generators in 1997, starting with the Band Name Generator. I gradually added several others. Most of them are based on a technique of multiple passes of replacing keywords in phrases. They start with a template, then replace keywords with plain text or another keyword phrase. This goes on until only plain words are left.
A key component to this is the large database of classified words. I started with about 300 words originally, and coded an interface for people to add more. As of September 2006, the database had more than 40,000 words. Although there are some people who add garbage words, the majority of words are appropriate. In 2005, I added a system that tracks votes on words. This allows visitors to help with editing. Words with low vote counts are not used. Words with high counts are used more often.