As a word of warning, I wrote this essay before reading Morgoth's Ring, which contains a lot of good information on this topic. Thus, I hope to rewrite this essay eventually, but it may be a while.
Upon even the most cursory reading of Tolkien's tales of Middle-earth, it is obvious that the world he describes is fundamentally different from our own. This distinction is not simply due to the presence of nonhuman characters or unfamilliar lands, for science fiction can supply the same and we still think such tales at least remotely possible. No, the difference is Magic, and we must come to some understanding of that magic before we can truly understand the world that Tolkien has given us.
To help myself find that understanding, I have attempted to classify all of the seemingly magical things and events in Middle-earth into groups of common character. (However, I have for the most part avoided drawing conclusions based on the actions of Ainur; godlike beings who gave shape to the world should probably not be expected to obey natural laws.) After much consideration, I have found that (in my mind, at least) most of them fall into one of three general classes.
The first class could be termed "technological": things that would not be entirely out of place in our world. The Doors of Moria could almost be built today using computer voice recognition, and the power of Saruman's voice could be nothing more than great skill with hypnosis. Depending on how far one is willing to stretch, it is possible to include a substantial fraction of the magic of Middle-earth in this category.
The second class consists of fundamental differences between the natural order of things in Middle-earth and in our own world. For example, although the details are never explained, we know that in Middle-earth there exist two worlds, one of the Seen and one of the Unseen (humans apparently exist almost exclusively in the former; the ringwraiths primarily in the later). Similarly, we know of several examples of true prophecy in Middle-earth, such as the dreams of Boromir and Faramir, Glorfindel's prophecy that "not by the hand of man will [the Witch-king] fall", and the Words of the Seer that so clearly foresaw the Passing of the Grey Company.
The third and final class encompasses all of the "active" magic that we see in Middle-earth. The Rings are perhaps the most obvious members of this category: they were created specifically to have a pronounced (and very real) effect on the world around them. The Mirror of Galadriel also belongs to this class, as do Finrod's "songs of power" against Sauron. (Gandalf's word of Command to hold the door of the Chamber of the Mazarbul is also a superb example, but as he is at least technically an Ainu I have for better or worse deemphasized his actions while drawing my conclusions on this topic.)
Having recognized these divisions, I find that the first ("technological") category has little impact on my thoughts about magic in Middle-earth. It simply does not differ enough from my experience to give me insight into the workings of Tolkien's subcreated universe. Therefore, productive discussion must focus on the other two.
In some sense, it is the intrinsic magical nature of reality in Middle-earth that puts it squarely in the realm of fantasy. Speaking of dragons as we are speaking of Middle-earth itself, Tolkien says in "On Fairy-Stories,"
"The dragon had the trade-mark Of Faerie written plain upon him. In whatever world he had his being it was an Other-world."
In this same sense, Middle-earth simply IS magical; asking how much magic it contains is a nonsensical question.
On the other hand, we may well ask just how different the intrinsic magic of Middle-earth makes it from our own world. It does not take long to realize that the lives everyday human beings in Tolkien's creation differ little from the patterns we see in our own history: the men of Bree sport no seers or sorcerers, and the Rohirrim trust in their valor in combat without the aid of magical lances and swords. Even their superstitions differ little from those seen in our world, although they certainly seem to hold more truth. All in all, it seems that the magical nature at the core of Middle-earth hardly affects our kind at all; its effects are seen most often in others more closely attuned to it.
One more example of a difference in the "natural order of things" deserves mention here. On their way back to Rivendell after the wedding of Aragorn and Arwen, we are told that Galadriel, Celeborn, Elrond, and Gandalf spent many nights conversing about ages past, but "they did not move or speak with mouth, looking from mind to mind." In his essay "Enquiry into the Communication of Thought" (published in Vinyar Tengwar 39), Tolkien discusses this ability at some length. Apparently, it was common to all thinking beings in Middle-earth, for we are told that
"Men have the same faculty as the Quendi, but it is in itself weaker, and is weaker in operation owing to the strength of the [body], over which most men have small control by the will."
While this ability might seem to be "active magic," its universality and lack of a "cost" for the user place it squarely in the realm of intrinsic differences between Middle-earth and our own experience. Note that in agreement with the conclusions earlier, Tolkien's comments (those quoted and others in the essay) make it clear that this ability did not have a substantial effect on the lives of most human beings.
This brings us, finally, to what may be termed "magic proper": the active use of abilities that would never be seen in our less colorful world. In "On Fairy-Stories," Tolkien discusses a distinction that he makes between different types of "active magic" (and compares them to ordinary mortal art):
...the more potent and specially elvish craft I will, for lack of a less debatable word, call Enchantment. Enchantment produces a Secondary World into which both designer and spectator can enter, to the satisfaction of their senses while they are inside; but in its purity it is artistic in desire and purpose. Magic produces, or pretends to produce, an alteration in the Primary World. It does not matter by whom it is said to be practiced, fay or mortal, it remains distinct from the other two; it is not an art but a technique; its desire is power in this world, domination of things and wills.
What Tolkien calls here "Enchantment" is clearly the ability that he ascribes to Elf-minstrels, "who can make the things of which they sing appear before the eyes of those who listen." It strikes me that this may be the same distinction that Galadriel makes when she comments that mortals speaking of magic "use the same word of the deceits of the Enemy," although her magic is clearly not the pure, artistic Enchantment of which Tolkien speaks above.
Despite the fact that Enchantment seems to be very closely associated with the fundamental nature of the Elves, it is rather difficult to find it directly in the books. Quite a bit of the Elf magic that we see could well be derived from it, but the published stories speak almost exclusively of magic involving at least some attempt to influence the Primary World. Both the Mirror of Galadriel and Finrod's song-spells of illusion against Sauron could fall into this category of Enchantment-derived magic.
There remain, however, quite a few examples of magic in Middle-earth which seem to have nothing to do with Enchantment. These examples, as noted above, all involve very direct manipulation of the Primary World, either by physical control or mental compulsion. In the case of the Great Rings, the primary purpose of this manipulation seemed to be the slowing of time (or at least of its effects). On several occasions, the Nazgul seem to have the ability to exert enormous pressure on Frodo's will, almost to the point of forcing his actions. After the capture of Dol Guldur, Galadriel apparently used some intrinsic power to "[throw] down its walls and [lay] bare its pits." On a lighter note, both Gandalf and Thorin display in The Hobbit a truly magical degree of control over their smoke rings.
Some insight into the nature and operation of this sort of magic can be gleaned from Tolkien's short story "The Faithful Stone," published at the end of his discussion of the Druedain in Unfinished Tales. After performing a clearly magical act involving a stone statue, the Drûg says,
"Alas! If some power passes from you to a thing that you have made, then you must take a share in its hurts."(11)
(followed by Tolkien's footnote:)
(11)"These tales, such as The Faithful Stone, that speak of their transferring part of their 'powers' to thier artefacts, remind one in miniature of Sauron's transference of power to the foundations of the Barad-dur and to the Ruling Ring."
This discussion seems to apply quite generally to any magic which affects the Primary World in Middle-earth: any such act, whether by Vala or Elf or Man, requires an investment of a part of one's self before it can be performed. What this "self" may refer to is certainly an open question, but it is clear that the various races of Middle-earth have very different levels of control over it.
With all of this discussion behind us, it is easier to draw conclusions about magic in Middle-earth, and in particular, about how "common" it might be. Again, I will break my summary up into three parts, corresponding to the three classes of magic discussed above.
First of all, the "technological" examples of magic in Middle-earth point to some reasonably common ability (at least among Elves and probably Dwarves) to create things whose operation is entirely beyond the understanding of virtually all human beings. It may well be that these things are creations of "active magic" as discussed above, but perhaps at a lower cost of "self" than the clearer examples presented there. Whatever their origin, they are not altogether uncommon: Bilbo obtains toys from Erebor to distribute at his Birthday Party which are "clearly magical." It is reasonable, then, to assume that some amount of practical magic is available to those who knew where to look.
Moving on, I observed earlier that the intrinsicly magical aspects of Middle-earth, while always present, play a very limited role in the everyday lives of the human beings who live there. For one reason or another (perhaps because humans typically "have small control over [their bodies] by the will"), humans simply are not generally even aware of these aspects of thier world. However, the situation for the Elves is apparently very different: their world is constantly filled with things that humans would call magic. It is even possible that the Elvish ability of Enchantment (discussed as "active magic" above) is another manifestation of Elves' closer connection to the magical nature of their world, and not "active" magic at all. In this sense, the amount of magic in Middle-earth really depends on whom you ask. As a last note in this connection, it seems natural to expect more supernatural events in a world that is still inhabited by beings who had a direct hand in its creation.
Finally, it seems that "active magic" (other than Enchantment) is also a universal ability. (At the least, the Ainur and many Elves have it without question, and the Druedain prove that it is not utterly beyond the capacity of our kind.) However, I believe that its use is very limited, due to the investment of "self" that inevitably goes along with it. Those who are able to practice it are surely all to aware of the degree to which they become bound to their creations, and of the dissipation of their innate "power" into other people and things. It is for this reason, I suspect, that we see so few clear examples of active magic in Tolkien's universe.
In conclusion, I have come to believe that magic (or at least the potential for magic) is a universal aspect of Middle-earth. It is this easy observation which allows to immediately understand that Middle-earth is fundamentally different from the world in which we live. However, its presence does not revolutionize the lives of those who live there: either like the Elves, they are a part of the magic, or like so many of the humans in the tale they are largely unaware of it. Finally, regardless of how common the ability may be, any decision to change the world by magical means is a significant one. The active use of magic is uncommon precisely because only the strongest motivations will make its use worth its price.