Magic can be anything that to an observer is incomprehensible.
If the U.S rolled into some third world country with these new tanks that emit burning sensations on their targets - to someone unfamiliar with the technology - that is magic.
IN regards to what most of us consider magic in fiction, there seem to be two major divisions. OK, let me rephrase - I am arbitrarily MAKING two divisions 
First, there is magic that any person COULD do, but very few have the knowledge to exercise it. In other words, it is just another skill and ability ranges all the way from those who have no desire/skill at it, but IF they put forth the effort, anyone COULD do it. And this type of magic has reproducible results that if anyone did it correctly, they could get the same result. Really, although it might involve other planes, etc. and we (as a reader or player) would call it magic because it could not be done in the real world, in the fantasy world it really exists as just another type of science or technology.
Then there are magic systems where a person needs to be born with a special spark, or somehow acquire some special ability. Think Harry Potter - either you are a Wizard/Witch or you are a Muggle. You can wave a magic wand and say "Wingardium Leviosa" perfectly and nothing will happen if you don't have "the gift". However, again within the Wizarding community, even though each individual seems to have a talent towards certain magic, it appears that it is based on technique rather than luck, and with skill and practice you can get good at anything.
Wait, scratch that. Some skills are that way, but there are some talents in the HP world that you either have or you don't even within the Wizarding world. Such as parseltongue (ability to speak to snakes).
Not sure what point I am making if any, other than to answer the OP "What is magic?" Well, to me, essentially it boils down to being able to do certain things that the majority of people can't. And it really only is "magic" to the outside observer, to those who can do it it is just another field of study. Someone who is a dunce at Hogwart's would be quite amazing to most Muggles, even if they could not control exactly what they were doing! Yet in their world they are just considered an oaf. Yet even within the wizarding world, HP's ability to speak to snakes is considered "remarkable". So even within the group of those that can do magic, I would guess that anything they can do themselves doesn't seem "magical" at all, while something that they cannot do probably seems really impressive - magic!
It's probably kind of that way in the real world. We ignore the magic we can do as ordinary, and marvel at those who can do things we can't. probably too much.
