"Burning the Bootloader
To burn the bootloader, you'll need to buy an AVR-ISP (in-system programmer), USBtinyISP or build a ParallelProgrammer. The programmer should be connected to the ICSP pins (the 2 by 3 pin header) - make sure you plug it in the right way. The board must be powered by an external power supply or the USB port.
Make sure you have the right item selected in the Tools | Board menu. Then, just launch the appropriate command from the Tools > Burn Bootloader menu of the Arduino environment. Burning the bootloader may take 15 seconds or more, so be patient.