What is Ambient Occlusion?
Per definition

Ambient occlusion is an approximation of global illumination that
emulates the complex interactions between the diffuse
inter-reflections of objects. While not physically accurate (for that
use full global illumination)

What is it?:
It is a way to make objects in a scene look more realistic. Ambient occlusion casts shadows where objects are close to each other. Note that it will also cast light where they are not. Ambient Occlusion is a fake light.
  

Note that in Cycles there is also an Ambient Occlusion Shader:

The ambient occlusion node gives per-material control for the amount
of AO. When AO is enabled in the world, it affects all diffuse BSDFs
in the scene. With this option it's possible to let only some
materials be affected by AO, or to let it influence some materials
more or less than others.


Ambient Occlusion enabled in the world panel.


Ambient Occlusion can make a big difference especially in the Blender Internal Render Engine. In cycles enabling Ambient Occlusion does not make a big difference in terms of realism because Cycles is already rendering with Global Illumination, which is physically correct Ambient Occlusion. So in cycles there often is no need for it whereas in the Blender Internal render engine it is very useful.