I think the term comes from the related expression "automagically." Magic is something unexpectedly good that happens behind the scenes to make a program work. Magic is the opposite of "gotchas", something unexpectedly bad that happens behind the scenes to break a program.

For instance, case sensitivity can be a gotcha for Windows users logging in to a UNIX webserver. Case insensitivity can be magic for UNIX users logging into a Windows webserver.