When a Level is being Built, it has to know how Lights will bounce off objects, what makes a shadow, etc. Computing Visibility is the step where the Engine looks at all of the Lights, makes note of the shapes around them, and creates shadows, bright spots, etc. as necessary. This is the third major step for Levels, as without it, your levels would be awfully dark. :)
Discussion
inio: I thought Computing Visibility was when the engine built the node visibility lists for each BSP partition. It then uses this information to do optimize the number of lights it has to consider for each surface.
Foxpaw: I think that UnrealEd 3 also does some of the lightmap calculations during this phase.
Dark Pulse: Well as I had stated when I typed the first revision, I wasn't totally sure if I was correct or not. I know it's something along those lines though.