A Theme is a categorization scheme or area of interest or focus of sets or creations (official, or fan created). Some of the more popular themes are Trains, Castle, or Space whose categorisation comes from LEGO themeselves.
Some themes, however, are "fan created" meaning that the fan community invented them, for example Mecha or Sea Monkeys. These are generally categorised or sub-categorised by the creator (or creators) of the theme.
Some themes are further catagorized by fans as licensed themes if they are designed by LEGO under contract with a third party.
(note, this would be greatly improved by some links into some of the theme specific categorization stuff on Peeron or LUGNET or elsewhere)
See the Themes category for more info.