A while back, I found out about the Google Apps service that allows you to host Google applications, such as Mail, Chat, Calendar, Sites, and Docs using your own domain name. I set this up for erichmusick.com and have been using it for quite some time. I'm hoping to set this up for my fiancee, Ellen, once we get married. She's a big fan of Gmail's themes, so I wanted to make sure Google made this functionality available in Apps Mail. When I looked in my Settings initially, I did not see the option to use a different theme. After doing a little digging, I found out how to enable themes for my domain's Google Mail application.
I cannot guarantee that this will enable themes for your instance of Google Apps Mail. However, this is what worked for me and, assuming that Google has rolled this out to all their Apps users, this should work for you as well!