Microcontrollers are usually programmed through a programmer unless you have a piece of firmware in your microcontroller that allows installing new firmware without the need of an external programmer. This is called a bootloader.
If you want to use the full program space (flash) of the chip or avoid the bootloader delay, you can burn your sketches using an external programmer.
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.
Here are some instructions on bootloading the Mini, thanks to Gian Pablo Vilamil.
Windows XP may be polling your parallel port and disrupting the bootloader burning process. You'll need this registry patch:
[HKEY_LOCAL_MACHINE\SYSTEM\ControlSet001\Services\Parport\Parameters] "DisableWarmPoll"=dword:00000001
See this forum thread for details.
There are different versions of the bootloader - both in order to work on different hardware and because it has changed over time.
The current bootloaders (i.e. the ones included in Arduino 0009) are almost identical for the Diecimila and NG (with ATmega168). They both run at 19200 baud and take up 2 KB of flash memory on the ATmega168. The only differences is the time the bootloader waits for a new program to arrive and the number of times it flashes the pin 13 LED when it starts. Because of the automatic reset on the Diecimila, its bootloader needs only wait a very short amount of time (less than a second) - to save time, it also flashes the pin 13 LED only once. The NG bootloader waits about 6-8 seconds and flashes the LED three times.
The bootloader that actually shipped on the Arduino NG is slightly different. It enables the internal pullup resistor on pin 6, and doesn't enable the internal pullup on the RX pin. Nor does it timeout upon receiving invalid data, so if you send data to it immediately after it resets, your sketch will never start.
The Arduino BT bootloader does some initial configuration of the bluetooth module.
The ATmega8 bootloader only takes up 1 KB of flash. It does not timeout when it receives invalid data, you need to make sure that no data is sent to the board during the 6-8 seconds when the bootloader is running.
Some ancient versions of the bootloader run at 9600 baud (instead of 19200). In order to successfully upload sketches to boards with this bootloader, you'll need to change the serial.download_rate in your preferences file to 9600.
Third parties have also worked on the bootloader. This page is link to some other bootloader development
The "Burn Bootloader" commands in the Arduino environment use an open-source tool, avrdude. There are four steps: unlocking the bootloader section of the chip, setting the the fuses on the chip, uploading the bootloader code to the chip, and locking the bootloader section of the chip. These are controlled by a number of preferences in the Arduino preferences file.
For the ATmega8 bootloader, these are:
For the ATmega168, these are (where <BOARD> is either "diecimila" or "ng"):
The AVR bootloader source code and SAMD bootloader source code are available.
