A description of something, which once set in motion, needs little or no further intervention. A machine that is able to make decisions by itself.
In terms of robots, it means those with some intelligence and ability to respond to their surroundings. A remote control vehicle is not autonomous and is better described as a ROV.
Some say one of the biggest failing of Robot Wars is the fact that none of the robots have any degree of autonomy, although the (good) argument to this is safety. An autonomous robot battle event would at the minimum require a remote to be sending a constant signal to allow power.