Building on what everyone else has said:
- The supernatural genre incorporates elements that cannot be understood by science and operate outside the rules of the real world
Supernatural fiction normally concerns itself with matters of god, the soul, archangels, and resurrection. Subgenres include supernatural horror fiction (i.e. the work of H. P. Lovecraft), Gothic (i.e. Frankenstein), ghost stories, supernatural thrillers, and other macabre stories in the horror genre.
- The paranormal genre of literary fiction includes beings and phenomena that are outside the realm of normal scientific understanding of the natural world.
Though the paranormal genre may include supernaturalist elements, this fiction genre generally includes creatures that have been popularized by folklore, fairy tales, and popular culture, such as fairies, aliens, shape-shifters, and the undead.
So, the key is supernatural = godlike/deity and themes that you normally find in religion and myths – things that can never be totally answered by science and modern learning
paranormal = fairy tales, folklore and urban legends. These topics might someday be explained (ie. ufo phenomena)