What must occur in order for work to have happened?

There must be a force applied, and there must be motion in the direction the force acts. You have to specify the direction because, for example, consider a satellite in a circular orbit. There's always a gravitational force on it, toward the center of the Earth, but the satellite never moves in that direction, so gravity does NO WORK on the satellite.