The labels are stored in ~/.gconf/apps/evolution/mail/%gconf.xml. Here's the defaults, plus 1:
<entry name="labels" mtime="1254501809" type="list" ltype="string">
<li type="string">
<stringvalue>I_mportant:#EF2929|$Labelimportant</stringvalue>
</li>
<li type="string">
<stringvalue>_Work:#F57900|$Labelwork</stringvalue>
</li>
<li type="string">
<stringvalue>_Personal:#4E9A06|$Labelpersonal</stringvalue>
</li>
<li type="string">
<stringvalue>_To Do:#3465A4|$Labeltodo</stringvalue>
</li>
<li type="string">
<stringvalue>_Later:#75507B|$Labellater</stringvalue>
</li>
<li type="string">
<stringvalue>_Junk:#42b2adbc5aa4|_junk</stringvalue>
</li>
</entry>
I added junk from within the evolution preferences window. When I add an entry manually here, or when I change the order of the entries, they appear to be overwritten by something. Even changing the 'mtime' attribute - the attruibute gets reset to it's 'pre edited by me' value.
Using gconftool-2:
gconftool-2 --dump /apps/evolution > mail-prefs.xml
edit the xml file in your favorite text editor. Then:
gconftool-2 --load mail-prefs.xml
This worked for me on ubuntu 9.05, evolution 2.26.1