Autonomous robots can act on their own, independent of any controller. The basic idea is to program the robot to respond a certain way to outside stimuli. The very simple bump-and-go robot is a good illustration of how this works.
This sort of robot has a bumper sensor to detect obstacles. When you turn the robot on, it zips along in a straight line. When it finally hits an obstacle, the impact pushes in its bumper sensor. The robot's programming tells it to back up, turn to the right and move forward again, in response to every bump. In this way, the robot changes direction any time it encounters an obstacle.
Advanced robots use more elaborate versions of this same idea. Roboticists create new programs and sensor systems to make robots smarter and more perceptive. Today, robots can effectively navigate a variety of environments.
Simpler mobile robots use infrared or ultrasound sensors to see obstacles. These sensors work the same way as animal echolocation: The robot sends out a sound signal or a beam of infrared light and detects the signal's reflection. The robot locates the distance to obstacles based on how long it takes the signal to bounce back.
More advanced robots use stereo vision to see the world around them. Two cameras give these robots depth perception, and image-recognition software gives them the ability to locate and classify various objects. Robots might also use microphones and smell sensors to analyze the world around them.
Some autonomous robots can only work in a familiar, constrained environment. Lawn-mowing robots, for example, depend on buried border markers to define the limits of their yard. An office-cleaning robot might need a map of the building in order to maneuver from point to point.
More advanced robots can analyze and adapt to unfamiliar environments, even to areas with rough terrain. These robots may associate certain terrain patterns with certain actions. A rover robot, for example, might construct a map of the land in front of it based on its visual sensors. If the map shows a very bumpy terrain pattern, the robot knows to travel another way. This sort of system is very useful for exploratory robots that operate on other planets (check out JPL Robotics to learn more).
An alternative robot design takes a less structured approach -- randomness. When this type of robot gets stuck, it moves its appendages every which way until something works. Force sensors work very closely with the actuators, instead of the computer directing everything based on a program. This is something like an ant trying to get over an obstacle -- it doesn't seem to make a decision when it needs to get over an obstacle, it just keeps trying things until it gets over it.