The ATMega644 has only 3 ways to be natively programmed: High voltage, JTAG, and ISP (confusingly referred to as serial programming in the Atmels docs). All those modes are hardware based. It basically means that you can't brick a device as long as you can use these programing modes (well at least HV and ISP). To these modes, we can add another one, software based. The AVR bootloader functionality, controlled by fuses, is simply a regular section of flash that can be protected of re-writing and have the MCU execute from that section instead of the normal boot location at 0x0000. Using your own code in there means you can reflash using every conceivable way like using the UART or your own funky GPIO based protocol.
The recommended method is to use ISP and one of the best programmer out there is AVRISP MKII (34$, though the STK500 is just as great, just a bit bulky).
ISP is limited to about 1/4th the speed of the master clock of the AVR. If you have a blank, never before used AVR it's generally safe to set the ISP speed to ~125KHz for the first time you try to program the device and set the fuses. Note that if you set it higher you can get erroneous results talking to the AVR, or worst case flip some bits you don't want flipped and make it somewhat tricky to regain control of the AVR. (Most frequently this happens by setting the oscillator to a setting that is incompatible with the hardware you're using.)
Once the AVR has been programmed and the fuses set, it will be running from the 28.636MHz clock, so you can safely turn up the ISP frequency up to 4MHz. That speed lets you erase and reprogram the entire ATMega644 in just about 2.5 seconds. (Which is really nice if you're doing a lots of little experimental downloads!)
Also, on the AVRISP MKII, you'll have two green lights if the USB connection is good and power is good on the target (Uzebox). If the light farthest away from the USB plug is red, power on the target is most likely off. If it's flashing orange you have the ISP cable on backwards. It's worth mentioning as well that if the AVRISP MKII is attached but disconnected from the USB on the host computer it will in all likelyhood hold the AVR in reset (preventing any code from running).
Using a bootloader eats flash and will always be slower that using ISP. In fact, using the UART/FTDI is 4x slower than using ISP.