What are Atmel Fuses?
I see blalor already has an excellent answer for the purpose of Atmel fuses.

To answer the follow-on question of "are they physical fuses or are they software programmable", the answer is neither.
All modern Atmel and Microchip microcontrollers store the "fuse bits" in nonvolatile memory cells -- physically the same as SLC flash cells.

When you use a chip programmer to download a new program into the microcontroller program Flash memory, it also erases and re-programs those fuse bit memory cells.

However, the software running on a microcontroller cannot change the fuse bits -- not even if you are using a "self-programming" microcontroller -- i.e., a microcontroller that allows bootloader software running on it to re-program its own program flash memory.

Some Atmel processors (especially the low-power ones) allow software running on them to change the clock source on-the-fly by writing to some configuration register -- but whenever they are reset (or the power goes away and then comes back), they go back to using the clock source specified in the fuse bits.
The only way to change those fuse bits is with a chip programmer.

Decades ago, those configuration bits (and the program memory as well) were actually stored in fuses -- a bunch of thin strands of metal; appropriate ones were selectively "blown" by applying 12 V until the metal melted and disconnected and the bit became non-conductive.
As you have probably figured out, that make the microprocessor one-time programmable (OTP) -- the only way to un-blow a fuse was to throw the entire microprocessor away, pull out a fresh new one, and start all over.

We still call those configuration bits "fuse bits" for historical reason -- much like we often call the program memory "ROM" (even though it's not really "read-only" on a self-programming microcontroller), and we have "solid-state relays" that have no moving parts, and "telephone companies" that spend only a small fraction of their time actually dealing with sound, and "computers" that spend most of their time displaying pictures and playing music rather than, you know, computing numbers.