Most of physics becomes easier as soon as you realise that some things are always the same: energy, mass, charge, etc. Thus we tend to think of these quantities as flowing from one place to another, i.e. if it disappears from here in this instant, it will be somewhere very closeby in the next instant. However, a brief thought experiment will reveal otherwise. Consider two masses suspended over a pulley in a gravitational field -- then a change of position (and potential energy) in one will be transferred (potentially) to somewhere entirely different.
But how local is local? Special relativity can be interpreted to say that nothing, including information, can travel faster than the speed of light. So in the experiment above, the effect is still local -- the speed at which the propagation of a mechanical wave through whatever medium the two masses were joined is still less than the speed of light. We could say that the "string" took up our slack.
So really, in our current context, nonlocal should be taken to mean an effect from a cause that travelled there faster than the speed of light (in violation of special relativity). It should be noted that in the heyday of special relativity, classical physics had reached its epitome. The seven equations of classical mechanics had been established and the world should have been a clock. However, quantum mechanics screwed that up nicely. From very early on, it became apparent that if you create a pair of photons (a photon and a anti-photon (which is actually a photon too, since photons are bosons) partner) they will have paired spin. This is the quantum version of convervation of angular momentum. However, as things are with quantum effects, we don't know what spin the two particles have until we measure one, but we do know that they have to have opposite spins -- they are entangled. So actually the act of measuring one spin has determined the spin of two particles. The next part is obvious: we send one somewhere suitably far, say Andromeda, and measure the spin -- instaneous transfer of information, and nonlocal conservation. Of course, we can't get to the Andromeda quickly enough, but we can (as it has been done) pull them apart to about 100km. We even measured it. It really does travel faster than the speed of light.