What does exposure compensation do?

Although I agree with the technical aspects of the other answers, I still prefer to explain "exposure compensation" in lay terms as a way to impose a disagreement with the camera opinion about the shot. :o)

Every time you point your camera to a scene, it tries to calculate how much light should hit the sensor in order to obtain a well balanced (again, according to the camera calculations) picture but allowing a fast enough shutter speed so the risk of blurring it due to vibration or subject movement is minimized.

In the progam mode (P) The camera uses something like this in order to decide the settings for a scene:

1. Set the shutter speed to something fast enough (say 1/50s) and ISO to the smallest value (say 100).
2. Increase the aperture until there is light enough for the scene.
3. If it reaches the largest aperture then start increasing the ISO speed (assuming it is in Auto mode, not fixed by you) until there is light enough for the scene.
4. If it reaches the largest ISO then start slowing the shutter speed until there is light enough for the scene.

In the aperture and shutter priority modes (A or Av, S or Tv) the aperture or shutter speed are set by you and the camera defines the other two parameters using the above logic.

That means that if the scene has enough light you will end with sensible settings for the three parameters (ISO, aperture and speed) and things tend to work out well.

But most of the times things are not that pretty. Either you get too much light (beach scenes, snow, backlights etc) or too little (dark places, night shots etc) and the camera calculations starts to work against what you may consider a nice shot.

This is where exposure compensation can help you. By tweaking with it you can either explain to the camera that you want it to consider less light in the calculations (moving the compensation to negative values) or to consider more light (moving the compensation to positive values).

The bottom line is, exposure compensation is an easy way for you to influence in the camera calculations in order to make it do things closer to what you want then what it would assume was "correct".

If I take a photo with a given shutter speed, aperture, and ISO, and then take the same shot with +1EV or -1EV, what is actually happening?

Note that in order to set all the three elements (speed, aperture and ISO) you would have to be in Manual mode (M), where there is no exposure compensation controls.

OTOH, if you fix one or two of them, the rules described above apply.

Is this just a gain control on the sensor?

No, that would be the ISO. Exposure compensation is about how much light will make part of the picture, ISO is one of the ways to control that.

Can you achieve the same thing by changing ISO?

Only if you are in Manual mode, otherwise the change in the ISO would only alter the balance between the other two factors (aperture and shutter speed). In Manual mode the change in ISO would indeed change the amount of light captured, so it would impact in the brightness of the picture.