how often should they be changed?? I believe Im losing power and that this may be the cause

Well, it'll vary on driving type, engine condition, fuel run, etc etc etc, blah blah blah. I change mine probably every 5k miles. I also change my oil every 1500 miles, or more often and do so with some Mobil 1 and Bilstein RS2000 treatment. If you drive it like you stole it, its best if you change/check the fluids and other maintenance items more often.

I think it's every 2 oil changes 6000 or 3 :P I suggest checking up on them every couple thousand miles though so see how they're doing and to readjust the gap. After awhile the gap will widen so you gotta make it smaller again. Also you can check how you engine is running by taking the plugs out and examining them:
black=rich
grey=good
white=lean

Since your gonna take em out also you might as well do a compression test if you got the gauge. Use anti-seize and I guess tighten it till it stops then 1/8 turn I think. Haha just saying that cuz I broke the threads off of one of my spark plugs recently and it was quite a challenge getting it out.