I just checked my account and don't see it yet. Gmail often does slow roll outs of new features across their data centers. Hopefully I will see it within the next couple of days.
One of my accounts has themes my primary account doesn't yet. I'm excited it looks really good. I'd been wondering for a while when Gmail was going to do themes like iGoogle does.
Nevermind... just found my answer; it's browser dependent:
Gmail Themes aren't yet compatible with all of our supported browsers. Themes are only available in Internet Explorer 7.0+, Firefox 2.0+ or Safari 3.0+, and Google Chrome. You won't see a 'Themes' tab in your Settings if you're not using the newer version of Gmail on the browsers listed above. Please note that Themes are not available if you're using Internet Explorer 6.0