I use a pair of needle-nose pliers. Set the watch face down on a soft towel. Open the pliers so the points fit in opposite grooves on the watch back and, while applying firm downward pressure, spin counterclockwise like you would expect. You'll have more room if you remove a pin from the band, but you can do it either way. Be careful though. The watch may be titanium, but it will scratch if you let the pliers slip.
The battery is easily accessible at this point.
pcHavoc
March 2011