do I still need a transistor if I'm using a relay?
Yup. The relay coil usually needs more current than an Arduino pin can supply, so you use an external transistor (like a 2N2222) to switch the relay. There are examples in the Playground area of the site for wiring this setup (one of these days I need to figure out how to export Eagle schematics for easy inclusion in forum postings, but today is not that day).
You could use the relay either to switch the positive side of the power going to the servos, or to connect the ground. You do still need to make sure that the servo and Arduino grounds are connected when you're running the servos, because there's a logic signal between them.
I took a look at the datasheet zoomkat linked to, and that actually looks like a good possibility, unless you're running a lot of servos. The problem with solid-state switching in uses like yours is that there's a loss of energy in the transistors: the Darlington transistors most commonly used can lose as much as 2V under heavy load. But the MTP3055VL only wastes about .2V for each Amp of load, which will almost certainly be acceptable for your purposes.
You could use it to switch the ground on the servos, and wire it up just like you would the transistor that controls the relay in the approach I originally suggested.
Make sure that you shop for the MTP3055*VL*: there are some flavors of MTP3055 that don't have "logic level" turn-on thresholds, and won't be as efficient if you try to turn them on with an Arduino pin.