I was wondering if there is someway to have relay-like behavior, but without constant power to the relay. For example, if my understanding is correct, if I wanted to control power from an outlet using a relay, it would either be normally on or off, but when power was applied it would switch to off or on respectively. Is there a way to achieve the same type of behavior but without constant power? For instance, a pulse of power would switch the "relay" to on, and another pulse would switch it to off?
Digik-Key has lots of power latching relays. Go here and under Coil Type select single or dual coil, and Coil Voltage 5VDC. Here's a dual coil one for about $4. Note the hefty coil current though (150 ma), so you'll need to drive each coils with a transistor.
Although it will take two output pins (and two transistors), dual coil is probably a better way for you to go, since I assume the single coil ones work by operating the coil in one direction, and then reversing the current to disengage -- which would require an H-bridge.
Aside from the everyday latching relays which have either one coil (reverse the polarity and pulse to change the state) or two coils (pulse one for 'on' and the other for 'off') there exist alternating latching relays. Each pulse reverses the state of the switch. The Tyco (née Potter and Brumfield) ones I show below have 120VAC or 240VAC coils available (as well as DC) and operate microswitches to switch substantial (15-20A) AC current. As you can see, the mechanism is completely open and somewhat resembles that of a ball-point pen or alternating switch.