so i was playing with UARTs on an atMega8 last week making a PWM motor controller. (will document the process soon. promise.)
so i'm presuming the AVR ISP programmer you are using is the same as mine here. mine connects to MOSI, MISO and SCK (pins 17,18 and 19 on the atMega8).
so the UART works on the RXD and TXD pins (pins 2 and 3 on the atMega8).
(i'm guessing Jesse's robostix uses a boot loader to upload the program through the UART.)
so, what you will need to do, get a max232 level shifter to convert the AVRs ttl voltages to the higher voltages needed for a PC serial port.
hook it all up like this: http://homepage.hispeed.ch/peterfleury/avr-uart.html
once you have that done and since you are using the AVRlib code, have a look at the example code in this file in the AVRlib package:
if you have any more problems let me know as i have this working at the moment.
interestingly enough, i couldn't get accurate enough timing with an external cristal while using the UART so i have to use the internal oscillator.
with the external cristal i was just getting junk through the serial connection unless i slowed the baud rate right down.
obviously i'm doing something wrong but i can't work out what.
anyway, it works fine for me with the internal oscillator.