Connecting AVRISP MKII programmer
Does this indicate that I have to connect the microcontroller's Vcc pin to 5V and then connect the programmer's Vcc pin to the same microcontroller pin? 


Yes.


  Also, does the power supply have to be exactly 5V?


No, based on its documentation here, AVRISP MkII supports target voltages from 1.6V to 5.5V.