J'ai enfin (à peu près) compris comment créer un thème Beamer from scratch. Voilà la méthode (ce n'est en aucun cas un lexique de commandes). Pour les différentes commandes, ça se trouve facilement (ici et ici par exemple). J'écris cet article car il n'y a quasiment aucune ressource qui explique comment créer un thème entier (juste comment en modifier des existants).


Tout se passe dans les fichiers suivants (remplacez Theme par le nom de votre thème):

Chaque fichier comporte la ligne :
\ProvidesPackage{beamercolorthemeTheme}[AAAA/JJ/MM] (color pour le fichier colortheme, à remplacer par inner, outer ou rien)

Le fichier principal est beamerthemeTheme.sty, c'est lui qui définit tout le reste (il contient les liens vers les trois autres fichiers de thèmes). Pour indiquer au compilateur d'utiliser votre fichier de thème, insérez la commande suivante \usetheme{Theme} dans la partie \mode<presentation>{}.

Pour la structure des slides (fond, menu, etc...), ça se passe dans outertheme. Par exemple, pour définir le fond des slides :
\pgfdeclareimage[height=\paperheight,width=\paperwidth]{frame_bg}{frame_bg}
\setbeamertemplate{background}{\pgfuseimage{frame_bg}}
On définit une image (frame_bg.png) de la taille du slide (height=\paperheight,width=\paperwidth), puis on la met comme fond de chaque slide.

Voilà pour une brève explication de la méthode. Pour des explications des différentes commandes, je vous conseille l'excellent site mcclinews.free.fr, qui est complet et détaillé. Le passage sur les beamercolorbox est très intéressant et utile. Enjoy !