Yes, you can reprogram the chip. I did the same when I upgraded my Arduino from a 168 to a 328 two weeks ago. The chip works great in another application.
Take note, of course, that you may need to change fuses depending on what kind of board you had and what kind of board you are moving it to. The most common, I would imagine (and the ones I had to reset) dealt with changing to the internal oscillator and setting dividers instead of using an external crystal. There is no comprehensive list of fuse changes, though, because it depends on what kind of circuit you're moving the chip to. YMMV.
As JohnC said, yes, reprogramming of fuses should be done BEFORE you remove it from the Arduino. Since the Arduino is fused to use an external oscillator, the chip will not do a darn thing if placed on a board without an oscillator.
The Arduino is basically just an Atmel AVR microcontroller, with just enough support electronics to allow it to operate. The AVR has built-in flash to allow it to keep programs with the power off, but to program an AVR chip directly you need a tool like the STK-500 to do the job. The Arduino overcomes this by also having a small USB interface on the board, and the Arduino boot-loader code already on the chip. This allows the PC side application to transfer your programs to the device, and in essence, have it flash itself.
So, bottom line, if you get an Arduino, the boot-loader is already there, and does its job automatically. You code your program on the PC, press the 'upload' button on the IDE, and within a few moments your program is running on the Arduino. The boot-loader does its job completely transparently.
fwiw, I personally have an Arduino 2009, and an STK-500 and can do on-the-metal programming on AVRs, but have found no need to bypass the Arduino's bootloader.
There is an actively developed free and open-source Arduino bootloader / firmware called OptiBoot, that might be of interest. From their site:
Many Arduino / clone boards now ship with OptiBoot instead of the classic Arduino firmware, though not necessarily with the latest and greatest version of OptiBoot. Existing boards can also be upgraded with OptiBoot if desired, procedures are documented at the linked site.
Also worth a look are the various bootloader enhancements on the AdaFruit web site. Not having personal experience with these, I can't really say much about AdaBoot, though.