The first I tried was Pixologic's ZBrush. I've seen a lot of fantastic work done in ZBrush, such as the strange alien creations of Kurt Papstein which I first saw in 3DArtist magazine:
I have tried a couple of times to grasp the basics of this software, but I find the interface very difficult to navigate and there are many terms, tools and other things that I have no hope of understanding without searching the internet, so I lost interest quite quickly.
I moved on to trying AutoDesk Mudbox, which seems a sensible choice considering you can easily export files from there into Maya. I also have free access to the student version which is always a bonus.
I found Mudbox much less frustrating and managed to pick up the basic controls. Because of it's visual similarities to Maya, it felt much more natural to me than ZBrush.
I started off modelling a face from a sphere, but for the next two I started with the basic bust shape. As I got more used to the controls it became much more like painting, and I was able to experiment more with shape and texture, using a variety of tools and by imprinting "stamp" textures onto the model.
It's very simple to switch to the paint tool and paint directly onto the sculpt in this program, which is much easier than texturing in a separate program such as Photoshop and then manually applying it, although some of the detail might be lost this way. I think it is useful for getting an idea of what colour scheme will suit the character.
I was fairly surprised to see how in a matter of hours I'd managed to develop from the first model to the third. I still haven't the slightest idea how I'd transfer a model like this into Maya and animate it, so that'll be the next step.