You should install the following (Debian/Ubuntu) packages:
binutils-avr includes most helper utility programs for cross developing AVR devices.
gcc-avr includes the GCC compiler that cross compiles to AVR code. Note that this does not include binutils-avr automatically!
gdb-avr includes the GDB debugger that is set up to cross debug AVR applications. It can talk to the JTAG ICE programmer for on-chip debugging!
avrdude is the programmer that we just mentioned.
avr-libc includes all the necessary C library object code in order of gcc-avr to work. It also includes the necessary header (include) files.
simulavr is optional, this is a software simulator so you can run your programs in an AVR virtual machine.