Good question.
I guess I could take the power directly from the 5V pin, although in that case I'd use an NPN to switch the relay. However, I am a little concerned about the amount of power the 5V pin can source. According to the Arduino Ethernet's schematic the 5V regulator is a Motorola MC33269ST-5 (the datasheet for which states output current "in excess of 800 mA"), but that's clearly not the regulator on my board. The regulator on my board just says 117-5, and there seems to be a ton of different 117-5 regulators out there, all with different max. output currents. Probably it would be fine, but then I'd rather know than guess...