Question
What is the story of Sharaba?
Answer
If you want to learn about the incarnations of Shiva, you can read the Shatarudra Samhita of the Shiva Purana, which mentions numerous incarnations including the following: Vrishabha the bull, whom I discuss in this answer; Virabhadra, the demon created by Shiva to kill Daksha after the death of Shiva's first wife Shakti; Kalabhairava, the demon created by Shiva to cut off Brahma's fifth head; and Sharabha who is the focus of your question.
The story of Sharabha is told in this excerpt from the Shatarudra Samhita of the Shiva Purana. It says that after Narasimha kills Hiranyakashipu and rescues Prahlada, his anger doesn't subside, so the gods, fearing that he will destroy the three worlds in his fury, ask Shiva for help. So Shiva sends his incarnation Virabhadra to subdue Narasimha. Virabhadra tries to reason with Narasimha, but Narasimha is committed to destroying the three worlds, so Virabhadra transforms into the half-lion half-bird creature Sharabha:
Then in a trice the form of Virabhadra became invisible.... Thereafter [the] middle [of Shiva's splendor] became clearly manifested in the form characteristic of Rudra of deformed shape.... He had a thousand heads and wore matted hair. His head was adorned by the cresecent moon. He appeared like a bird with wings and beak. His body was fierce and fully developed. His fangs were very sharp. Adamantine claws were his weapons. His neck was black in colour. He had huge arms and four legs. He was blazing like fire.... His three eyes were as wide and blazing as the fire of the evil spirit of great fury. His fangs and lips were clearly visible.
Sharabha grabs hold of Narasimha, taking him high up into the sky and then dropping him onto the ground. Narasimha then snaps out of his fury, acknowledges the power of Shiva, and then dies. The gods praise Sharabha, who tells them this:
It was Vishnu alone in the form of Man-lion, haughty and strong, engaged in the activity of annihilating the universe. He shall be prayed and bowed by my devotees aspiring achievements. He is the foremost of my devotees and the granter of boons.
After that Sharabha disappears and Virabhadra appears, tearing the hide off of Narasimha's body, which is said to be the hide that Shiva wears. And Narasimha's head becomes one of the skulls in Shiva's necklace.
Now the Shiva Purana's account ends with Sharabha simply disappearing after defeating Narasimha, but some versions of the story add a further incident, which is where Gandhaberunda comes into the picture: after Sharabha grabs hold of Narasimha, Narasimha in his fury creates a two-headed bird beast called Gandhaberunda which is even more powerful than Sharabha. Gandhaberunda defeats Sharabha in battle, and then Vishnu and Shiva finally call it a day.
Now Gandhaberunda is famous enough that he is depicted in the coat of arms of Karnataka, but I haven't yet found a scriptural basis for his story, which is why I asked this question. But in the mean time, you read the story of Gandhaberunda and Sharabha in this excerpt from the new Amar Chitra Katha comic "Divine Beings"; the above picture is taken from there.
Note: “The question: What is the story of Sharaba?” is licensed by Stack Exchange Inc (https://hinduism.stackexchange.com/); user contributions licensed under CC BY-SA.