If you are interested in magic as a device in The Tempest specifically (which it seems you are since the question is in The Tempest group), you should know that Prospero's "magic" is also symbolicaly linked to the magic or art of theatre. Many critics have noted that Prospero the magician is similiar in how he manipulates and controls the people on his island to a playwright (even Shakespeare himself) and how he creates and chooses and controls what shall happen in his play.
So, in this case, for Elizabethans (or anyone watching the play), the magic of Prospero demonstrates the magic of theatre. All of the special effects -- the shipwreck, the charming of the royals after they land on shore, the infatuation between Miranda and Ferdinand, the masque of the Goddesses -- all of these things are presented through the "magic" of theatre and are controlled by Prospero/Shakespeare.
Prospero's curtain speech at the end of the play, demonstrates the connection between Prospero and the creator of the play himself when he asks the audience to "free" him with their applause. He has been trapped by the magic inherent in the performance, and will only be free to leave at the audience's command. This, actually, gives the audience the ultimate magical power, and connects the character Prospero to the playwright Shakespeare.
It is interesting to note that some scholars surmise that this was, indeed, Shakespeare's final play, so strong is the parallel they find between Prospero leaving his magic garments behind and, potentially, Shakespeare deciding to leave his play writing behind. So, for Elizabethans, one of the primary experiences of magic, in relation to The Tempest, was through Prospero's theatrical use of magic as a device of the stage.
The Elizabethan world was caught between many ideas including superstition and science and religion.
Folk tales and stories of magic and miraculous happenings were still fresh in their culture. Even today in parts of the British Isles, people find "fairy circles" and speak of the little people.
Shakespeare tapped into the belief in the supernatural in many of his plays, A Midsummer Night's Dream, Julius Caesar, Macbeth, Richard III, etc. culminating with his farewell to theatre (or so it is believed) The Tempest, about a magician, a very powerful one who tells us he can raise the dead.....he just can't get off the island without the help of the storm which brings a ship to his island and, of course, his faithful servant, Ariel, a magical creature.
In the end, Prospero turns his back on magic. Perhaps this is a realisation that what was once "magical" can be explained by science. As the Elizabethans began to embrace science (Issac Newton comes to mind), the world of magic was reduced.
The kind of magical worlds Shakespeare created and similar fantastic worlds still exit in literature.