The basic reason is that local doesn't actually alter the contents of a variable. It allocates a new one and makes sure that the access path to the original variable now temporarily leads to the new variable. This means however that there has to be a primary access path to the variable, or the trick won't work. You also have to be sure that the original location will not disappear before the restore.
For package vars, this primary access path is the glob. Each package contains a glob for each name that occurs in it. This glob can contain a scalar variable, a hash variable, an array variable, an IO handle etc.
When you do local $Foo; (where $Foo is a package var) perl will save the original scalar variable (not its contents) on stack, create a new scalar variable, and insert it into the glob's SCALAR field. It will also increment the refcount on the glob so it will surely not be deallocated.
•(Update: a local doesn't get initialized with the original value... I thought it was..)
On return, the localized variable is discarded, the original variable is placed back in the glob, and the glob's refcount is decremented. Everything is back to normal.
Note that you can easily see this behavior: just take a reference to $Foo before and after localizing it. You'll see they reference different and independent variables. (Keeping a reference to the localized var will ofcourse keep it alive, even if the local has already been restored
The procedure is identical for local %Foo and local @Foo, except they operate on the HASH and ARRAY fields of the glob. When you do local *Foo, it does essentially the same procedure but for all fields of the glob at once. They're put together in a structure to which the glob keeps a pointer, so it doesn't need to save each var separately. Note that it can't just allocate a new glob and place it into the package, since all existing code would still use the old glob, which they reference directly.
Now for lexical variables... they have no glob! :-)
That doesn't mean it's truly impossible to localize them (I haven't examined how my-vars are implemented exactly), but it surely means that the mechanism described above can not be reused for them.
As I mentioned in my original note, localizing array and hash elements works completely different. Here you specify an array or hash in any way you like, and the index or key of an element. local $foo[3] then takes the scalar variable (again, not its contents) which is the element at that index (or key), saves it on the stack, along with a reference to the array/hash (which also means the array/hash will surely not get destroyed) and the index/key of the element. It creates a new scalar variable and places in the original location. When the block ends, it places the saves element back, discarding the variable that was there.
Again, you can check this by taking a reference. You'll see that the localized $foo[3] is a different and independent variable than the original.
Ok, that's it I think... any questions? :-)
•Update: Here's some example code with output: