Theme and Mechanics

Veneer is anything about a game that can be changed or eliminated without functionally changing the way the game plays.
Distinctive veneer allows players to distinguish certain components from other ones.
Representational veneer indicates that certain components are supposed to represent something in the real world.
Some veneer is both distinctive and representational (i.e. the shapes of the settlement and city pieces in Settlers).
Some veneer is neither distinctive nor representational (i.e. the shapes of the cards in Settlers).

Explicit theme is simply the sum-total of a game's representational veneer.
We can rate a game's explicit theme as highly abstract, highly concrete, or somewhere in between.
When we say that a game is highly concrete or thematic, we mean that it has a lot of representational veneer, and/or that the veneer maps to some real-world counterpart in very specific and detailed ways.
When we say that a game is highly abstract, we mean that it doesn't have much representational veneer, and/or that this veneer maps to some real-world counterpart in only general or simple ways.
Some games (i.e. Bridge) have virtually no representational veneer, and are therefore entirely themeless.

In addition to explicit theme, every game also contains an implicit theme.
A game's implicit theme can be discovered with the help of a technique called theme-stripping.
Theme-stripping is the mental act of imagining a game with all of its representational veneer changed into non-representational veneer. A theme-stripped game should consist of nothing but white components, marked only with black numerals, letters of the alphabet, and/or simple geometric shapes. No representational connection with the real world should be hinted at.
Imagine sending a theme-stripped game to 1000 playtesting groups who have never seen the game before in any form, and asking them what real world activity the game might represent. The game's implicit theme would be indicated by the most common responses from those 1000 groups.
Implicit theme represents an objective relationship between a game's theme and its mechanics.

A game's explicit theme should always complement its implicit theme. A game is thematically mismatched if its explicit theme is different than its implicit theme.
A game's explicit theme should always be at least as concrete as its implicit theme. A game is underthemed if its explicit theme is more abstract than its implicit theme.
A game is overthemed if its explicit theme is more concrete than its implicit theme. This is not necessarily a problem; in fact, virtually all games are overthemed to some extent.
A game is strongly-themed if its explicit theme and its implicit theme are both relatively concrete.
A game is abstract if its explicit theme and its implicit theme are both relatively abstract.
A game is weakly-themed if its implicit theme is relatively abstract, but its explicit theme is relatively concrete. Whether or not this is "bad" is largely a matter of personal taste.

There is no necessary antagonism between theme and mechanics in game design.
There is no necessary antagonism between theme and elegance in game design.
There are many starting points and many paths. Sometimes you begin by working on abstract mechanics, until an implicit theme begins to emerge (which may then suggest new changes to the mechanics). Sometimes you begin with a highly concrete explicit theme, and no mechanical ideas at all. Sometimes you know exactly how concrete you want the implicit theme to be, and sometimes you have no preference. Sometimes you develop your mechanics around an explicit theme, only to find that a totally different and unexpected implicit theme emerges, causing you to change your explicit theme.
Regardless of where you start or what path you take, analyzing your game in terms of implicit and explicit theme can help you get a handle on where you've ended up.