(covers information from several alternate timelines)
The Vulcan salute was a hand gesture used by Vulcans. It involved holding the palm of one hand outwards while placing the fingers in a "V" shaped by separating the middle and ring fingers, while keeping the others together.
When parties took their leave of each other, one party could use the phrase "Peace and long life" and still receive "Live long and prosper" as a reply. (TOS: "Is There in Truth No Beauty?", "The Savage Curtain"; TNG: "Sarek", "Unification I") Alternately, each party could simply state to the other "Live long and prosper, (name)." (TOS: "Amok Time"; VOY: various episodes)
In diplomatic situations, the greeting used was "I/We (depending on situation) come to serve," possibly prefaced by the statement of the initiators' name. The response was "Your service honors us." (TOS: "Journey to Babel"; TNG: "Data's Day", "Sarek", "Unification I")
In 2151, an ornament of Surak performing the Vulcan salute with both hands was displayed aboard the Vahklas, a Vulcan civilian transport ship. Unlike other Vulcan salutes, Surak's hands were not held upright. (ENT: "Fusion")
Several Humans greeted Vulcans with this gesture, including Captain Jonathan Archer in 2154 (ENT: "Kir'Shara") and Captain Jean-Luc Picard in 2368. T'Pol taught Trip the salute when she took him to Vulcan to meet her mother, T'Les (TNG: "Unification I"; ENT: "Home") Zefram Cochrane tried and failed to perform it in 2063 at First Contact; he settled on a handshake instead. (Star Trek: First Contact) The saying was quite well-known among those in Starfleet – in 2375, trapped in the Delta Flyer under layers of rock, two minutes before the air would run out, Tuvok told Tom Paris that "In accepting the inevitable, one finds peace," to which Paris responded that, if this was another Vulcan axiom, he would stick to "Live long and prosper." Fortunately, Paris had barely finished the sentence when he was interrupted by the sound of Voyager's phaser drills breaking through the rock, and those on board the Flyer were safely beamed back to the ship. (VOY: "Once Upon a Time")
As a practical joke, Tom Paris and Harry Kim once reprogrammed Tuvok's security console so that it said "live long and prosper" whenever he accessed the internal sensors. They also reprogrammed his replicator the same way. (VOY: "Revulsion")
In 2258, in the alternate reality brought about by Nero's incursion, Spock, after speaking with his younger counterpart, made the hand gesture but said "good luck" as he felt it would be "oddly self-serving" to say the usual phrase to himself. (Star Trek)
The Vulcan salute was devised by Leonard Nimoy, based on a gesture made by various Jewish denominations, including Orthodox and Conservative. Nimoy learned the gesture, which takes practice to do, from visiting his grandfather's synagogue as a child. According to Nimoy in the 1984 television special Leonard Nimoy: Star Trek Memories, the original script for "Amok Time" called for Spock to walk up to T'Pau and then they would exchange brief greetings. Nimoy thought this might be a good chance to bring something unique to the Vulcan people. When he spoke to the show's director, Nimoy remarked that as an example, like most people will shake hands, how military officers salute each other and Asians will bow to each other, perhaps Vulcans will do the salute that he remembered from his childhood and the director agreed to try it. According to Nimoy however, they ran into a problem when the actress playing T'Pau, Celia Lovsky, couldn't do the salute. According to Nimoy, they used a simple camera trick where her hands were below camera frame and she used her other hand to get her hand in the proper position and the salute would be born.
The gesture forms the Hebrew letter "Shin" and represents the name Shaddai, which means "Almighty (God)." The hand gesture is traditionally used by the Kohanim (Hebrew "priests"), Jews of priestly descent, during a blessing ceremony performed during the prayer service of certain Jewish holy days.
The Jewish blessing is done with both hands, with arms extended upward at roughly a 45-degree angle, rather than one hand held upright as in the Salute. The blessing is found in Numbers 6:22 of the Old Testament where God tells Aaron, Moses' brother, the first High Priest, to bless the Israelites and say, "May the Lord bless you and keep you. May the Lord make his face to shine upon you and be gracious to you. May the Lord lift up his countenance upon you and give you peace." (There are numerous common translations).
The grammatical format of the salutation is very similar to (and probably based upon) the Hebrew greeting, "Shalom aleichem" (peace be upon you) and its usual reply, "Aleichem Shalom" (upon you be peace). There also the Arabic version (As-Salamu Alaykum) and the Yiddish version (şolem aleyxem) of it, with roughly the same meaning.
William Shatner appears unable to produce the Vulcan salute. If you look closely at his hands in Star Trek III: The Search for Spock when he performs the salute, it appears that fishing line holds two of his fingers together. On the video William Shatner and Leonard Nimoy: The Twenty-Five Year Mission, Nimoy and Shatner joked about this with Nimoy saying "It took me years of diligent practice and self-denial to be able to do that." Shatner then quipped "So that's why I can't do it!"
In TV Land's The 100 Greatest TV Quotes & Catchphrases, Shatner described the salute as a benediction, comparing it to the Sign of the Cross. During a June, 2009 appearance on The Tonight Show with Conan O'Brien, Shatner demonstrated his inability to perform the salute, to which O'Brien responded with a perfect salute of his own.
The Filipino greeting "Mabuhay" can also be roughly translated as "live long and prosper" (it literally means "Live", but the expression is meant to convey a wish for someone to have a long and prosperous life in order to truly "live"). 
In Act 5, Scene 3, line 42, of Shakespeare's Romeo and Juliet, Romeo says to Balthasar, "Live, and be prosperous, and farwell good fellow." 
- The Jewish Origin of the Vulcan salute - a very complete page by Rabbi Yonassan Gershom, with photos and diagrams of how the salute forms the Hebrew letter Shin, the use of the Blessing Hands gesture on Jewish gravestones and jewelry, etc.
- Names of God in Judaism at Wikipedia shows a clear illustration of the Judaic origin of the Vulcan salute