Brand new ATmega8 - Changing Fuse Bits
[order]


Shouldn't matter. The AVR won't use the crystal until nRST is released, so you may as well hook it up first.


  [power]


That depends on whether or not the programmer provides power. If it doesn't then you'll need to do so.