I use photoshop. I try to create a cartoon style by drawing everything with the pen tool or using shapes, and then add stroke/shadow blending options to the layer. I'm pretty sure Tiyuri uses photoshop as well.

I don't create themes, but I created "lonely island" map. I use Inkscape, it's free and open source program to make vector graphics. You may download it from http://www.inkscape.org/. I'm sure you can create good themes with Inkscape.

Inkscape too, for the Castle map I use GIMP too, but that map is made using Inkscape only...

Adobe Fireworks CS3 :D

Adobe illustrator CS4

Forgot to mantion adobe Flash CS3.

..and MSPAINT!!!! :o (Yes, I'm serious.)

I highly recommend Inkscape on any graphic work you have to do.
It's a powerful and efficient tool, and it's getter better and better.
And, most-of-all, it's open source.