The Official Gmail Blog announced the release of themes for Gmail yesterday. It seemed they were not immediately available after they made the announcement, as it took several hours before I saw it appear in my settings. Perhaps because they did not want other blogs to steal their thunder.
I found it a little odd when the theme settings did not appear on my laptop computer after using Gmail from Chrome on my desktop PC where they did appear. However, this morning when I used Gmail on my laptop, the themes settings did appear. Google has been known to roll out new features with a phased approach in the past. It would seem that they do it at a browser level, rather than a user level, since I was able to see the changes on one computer but not on another.