Nuts N' Volts magazine has recently run 2 articles about this exact topic. They used picc i think, but the concepts are close.. Their robot used hobby servos, sumobot wheels, salvo RTOS, and some fairly simple looking code. If you cannot find it, i can tell you issue #s when i am at home..

basically their bot used just a 2-axis gyro, if i recall, and an AVR.. not a pic.. no PICC.. Hmm.. At any rate, you can checkout their code, it probably avoids Floating point math, which will help you.

There is another method out there that peopel seem to actually have some success using; which is to use 2 IR range sensors pointed at the ground... Seems much slower than a gyro\accelerometer.. but, what do i know..

hope that helps at least a little.
-R