The Search for the Lost Husband is a very widespread tale, closely related to Beauty and the Beast. Sometimes it seems like it's a default ending for fairy tales.
A woman marries a supernatural male being, who seems monstrous at first and might be enchanted in animal form, only appearing human at night. The wife breaks a taboo, and her husband vanishes. She then searches the world until she finds him and they are reunited.
A non-exhaustive list of stories falling into this category:
The hero is a woman, and her opponent is usually a woman - an enchantress who's trapped the husband, or a rival princess who wishes to wed him.
In their notes, the Grimms wax a little poetical on how the story is about the heart being tried so that "everything earthly and evil falls away in recognition of pure love." There's also an interesting note about, in this case, light being an ill omen and darkness being good. This goes back to the taboo. Often, she takes a candle and spies on her husband in the night to see his human form, or attempts to break his curse by burning his animal skin.
Karen Bamford has a good analysis. The wife's journey is an act of atonement; she does penance for sinning against her divine husband, and wins him back through toil and effort.
In many cases, her long journey takes her through some kind of otherworld. In an Arabic version, "The Camel Husband," the heroine goes to the land of the djinn. The land East o' the Sun and West o' the Moon is a place beyond the bounds of the physical world and the laws of nature. Psyche literally goes through hell.
This quest allows her to finally truly break the spell on her husband and resurrect him from a "metaphoric death" (Bamford). In many tales, the wife visits the husband during the night, while he lies in a drugged sleep, and tries repeatedly to awaken him. In "Nix Nought Nothing," the husband falls into sleep similar to Sleeping Beauty, and only the true bride can symbolically raise him from the dead with the power of love. In Cupid and Psyche, Cupid lies wounded for quite some time.
I found a Japanese folklore site that had an interesting perspective. (As seen through Google Translate, but whatever.) The groom's animal shape is the body, and his human shape represents the soul, but the soul belongs to the otherworld. Death and rebirth are required to truly bring it into the real world. So then you have stories like the "Frog King" or "The White Bride and the Black One" where the enchanted animal must be thrown against a wall or have its head cut off.
There are stories where a husband seeks a lost wife; this is its own tale type, AT 420, The Quest for the Lost Bride. A couple of examples are the Russian Frog Princess, and the story of the Swan Maidens. In Household Tales, the Grimms mention "a man in a Hungarian story, whose wife has been stolen from him, seeks [help], first from the sea-king, then from the moon-king, and finally from the star-king (Molbech's Udvalgte Eventyr, No. 14)."
Incidentally, Joseph Jacobs' version of the Swan Maidens also features the Land East o’ the Sun and West o’ the Moon, but that's from Europa's Fairy Book, in which he mashed up a lot of different traditions.
This website is based on my research into folklore. Home to the Thumbling Project, collecting different versions of Tom Thumb and Thumbelina from around the world.