I got the idea for my hexapod robot from the Insectronics book by Karl Williams. It is a very simple design, using only three servos for walking, and one for the head with an ultrasound sensor mounted on it.
One servo is connected to the front and back leg on the left, and one servo is positioned the same way on the right. The third servo is mounted on the bottom of the robot and connected to the two middle legs. This allows the robot to lift two of its legs off of the ground and then move them in the direction it needs to travel. A note for those wishing to build a similar robot, it is very difficult for the robot to lift itself off of the ground using a standard hobby servo. I would recommend using a quarter scale size servo like I did.
The theory behind the programming is fairly simple (making everything run smoothly with the walking gates is a little more complex), while walking forward the robot looks back and forth for an object in its path. If something gets in its path, it stops, does a full scan of the area, turns to the clearest path and continues on its walk.