The PC should recognize the MKii being plugged in.
If not, do the New Hardware install thing or Linux equivlent and use the drivers provided with Arduino, my path is:
c:\arduino-1.0.1\hardware\tools\avr\utils\libusb\bin
(might have the slashes backwards there)
You do have avrdude installed if you have the IDE running.
Yes, can burn & re-burn to your hearts content, up to 10,000 times or maybe 100,000 times, I don't remember the number in the datasheet.
I'd start with the MKii driver.