Today : What's magic ?
According to a terse definition of magic : it's when actions performed on a symbolic level produce an effect in the real world. (*) So what does magic mean in perl ? Well, it's the same thing !
More precisely, some variables are said to be magical when manipulating their values (something that's usually purely internal to the executing perl program) affects the "outside world", doing something else than changing or reading the stored values. For example, the %ENV hash is magical, because modifying it modifies the environment variables of your process. The %OVERLOAD hash is magical, because it modifies the way the perl parser behaves. The value returned by substr(), although not a variable sui generis, is magical as well, because changing it affects the the original string. Perl provide, with tied hashes and arrays, a way to add magic to your own variables.
Moreover, the word magic is also traditionally linked to wizardry, and that's exactly how one feels when one comes over the implementation of magic in perl's internals. (You may want to look at mg.c in the perl souce code, and at the Tolkien quote at its beginning.) If you want the details, the magic is actually a linked list of structures containing pointers to functions, that should be called on variable access or modification. The perlguts manpage details this topic.
(*) This is, quite shortened, an anthropological definition of magic. (It's broader than in the usual LoTR/D&D-style folklore, but nevertheless useful.) Basically, our scientific way to describe the world distinguishes the real world, and the world of symbols or words, that is a human creation. Operating on symbols, and producing effects on the reality, is called magic. Unless it's actually sufficiently advanced technology, of course.-]