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.
Tales of Faerie had a post a while ago on Beauty's request for a rose in Beauty and the Beast. The unique request differentiates Beauty from her materialistic and greedy sisters, who ask for clothes, shoes, or other expensive ornaments.
Some themes emerge when you look at different tales, and they might not be the themes you expect.
In most, she asks for a rose or other flower. Other objects close to nature might be a lily, a grape, or a green nut-twig. In "The Sprig of Rosemary," the heroine picks the titular sprig herself while gathering firewood. This is a simple request in contrast to her sisters' pleas for material goods.
Unless she asks for it in winter. Then it's a fantastical request that should be impossible to grant.
So her request is not necessarily simple, but impossible. The rose is the most common theme that I've found, but there are other versions that make this even clearer.
A singing, springing lark. Maria Tatar says the rose and the lark, like the rose, is emblematic of the girl's character. The rose symbolizes her inner beauty and the lark symbolizes her energy and liveliness.
A clinking, clanking lowesleaf. This is definitely a leaf; it's just the lowe part that's confusing. There is an impossibility implied, with a simple piece of plant matter clinking and clanking like a piece of metal.
Lowe might mean lion, but that's a guess. Similarly, the German for dandelion is Loewenzahn.
A pennyworth of “sorrow and love” in one English tale. Here she's asking for abstract concepts.
A slice of roach off a green meadow, from one Portuguese tale. This one baffled me for a long time, but turns out, it's a FISH!
There's a kind of fish called a roach. (Goraz is the word in the original Portuguese.) She is asking for a fish native to a green, grassy field - something that can't possibly exist.
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.