Russian salad is a potato salad with many variations to it.
In its most basic form, it is diced potatoes and cooked vegetables, mixed in mayonnaise. The vegetables are usually diced carrot and green peas, often canned or frozen.
Chopped meat is sometimes added. Any other root vegetables are usually diced. Beyond that, all bets are off, and anything can be put in. The mayonnaise might be even swapped for oil and vinegar. This is not a contemporary whim; oil and vinegar as an alternative dressing dates from the 1800s — see Literature and Lore section.
Classically, the salad “is put into a domed mould lined with jelly and decorated. After having been well chilled on ice, the salad is turned out onto a plate.”  The “doming” of the salad for presentation may stem from Olivier’s original presentation effort.
Russian Salad is incredibly popular in Russia, where it is referred to as Olivier Salad. There, it is a staple at all celebrations that involve food, particularly at New Year.
Up until the mid-20th century, North American recipes for it almost always called for various meats to be added, along with a plethora of other things. In the last half of the twentieth-century, there seems to have been a trend to simplify it down to potatoes, peas, diced carrot, and maybe one other vegetable.
Russian Salad has also has become popular in Spain, where tuna is added. Iranian versions usually add chicken.
Russian Salad bears no relation to Russian Salad Dressing.
The first mention that we have of a Russian Salad dates from 1858, though from the mention it is not possible to know what was in it.
“At a banquet recently given in Paris by a member of the Imperial family, the extravagance of dishes is said to have called down a reprimand from the emperor. One single dish called salade russe is reported to have cost over $1,000.” — Pen Pickings Column. Racine Daily News. Racine, Wisconsin. 19 March 1858. Page 2.
Despite that early mention, creation of Russian Salad is attributed to Lucien Olivier at the Hermitage Restaurant in Moscow, sometime after 1864 when he opened the restaurant. Or in any event, it was what he made there that served as the basis of the definition for what we now think of as Russian Salad.
“As for ‘Russian Salad’, as interpreted in western countries (i.e. diced cooked vegetables in or with mayonnaise), it was essentially a French-Russian creation called ‘Vinegrety’ which had a dressing of oil and vinegar. The salad to which Olivier gave his name involves cold game (or salmon in Lent) and has a more sophisticated dressing.” — Davidson, Alan. The Penguin Companion to Food. London: The Penguin Group, 2002. Page 810.
1905 comic in Le Monde Comique making
fun of the Franco-Russian alliance
shows the ubiquity of Russian Salad
In creating the salad, Olivier was assisted in the kitchen by Marius Olivier (relation uncertain.) He actually called this dish “Game Bird with Mayonnaise” ( «Майонез из дичи» ). In the centre of a platter was a mound of potatoes mixed with gherkins, covered with hard-boiled egg slices for decoration. Around this mound, he arranged slices of simmered grouse and partridge breast, small aspics moulded into bird shapes, simmered crayfish tails, and slices of tongue, all of which was drizzled with a mayonnaise sauce.
Olivier had reputedly intended the central mound really just to be decoration, but the diners took some of everything and stirred it together on their plates, and loved it. In doing so, his diners had actually completely changed the dish he invented. Olivier reputedly he was horrified, but he had a restaurant in Moscow to run, and Muscovites weren’t going to change their food preferences, so the next day, he combined everything, mixed it with mayonnaise and served it like that. 
Olivier does not appear to have written down his recipes, as other chefs of the era did; consequently, the recipe died with him at the young age of 45.
There are varied accounts that Olivier’s salad included items including capers, caviar, cucumbers, lettuce, smoked duck, soy beans, and truffles. This wouldn’t necessarily mean conflicting accounts: Olivier may well have varied the salad seasonally, and quite probably in fact did so according to the Orthodox Church calendar which proscribed certain foods during Lent, for instance.
In any event, most food historians seem to agree that Olivier’s mayonnaise sauce for it really was the key that no one seemed able to reproduce. Reputedly, he wouldn’t let anyone watch him make it, though this would mean that he either never took a single night off work ever, or that the salad was only available when he was present, or that he made up quantities of the mayonnaise before his day off in an era before refrigeration.There are hints that the sauce had a Provencal twist to it, though possibly that was just olive oil from Provence.
In any event, Salad Olivier as it was known, became the signature dish of the Hermitage Restaurant.
Literature & Lore
“Household Hints — Russian salad is made by cutting up raw apple and every kind of available vegetable into small slices, and laying them in a shallow dish with salt, a little vinegar and pepper and the best oil. The dressing must thoroughly maturate the mixture for at least twelve hours, and then the effect will be found very agreeable.” — The Herald And Torch Light. Hagerstown, Maryland. 5 January 1880. Page 3.
“Take the breast or drumsticks of a cold roasted or boiled fowl and cut fine; slice and cut four slices of ham or six of tongue; cut the meat in slivers; slice six good-sized potatoes; mince finely one sour apple; mix all these together; make either a Mayonnaise sauce or an oil and vinegar dressing; decorate with beetroot and olives; an excellent addition is two anchovies cut fine; do not add an onion, though the true Russian salad ought to have it.” — Russian Salad. In “Domestic Matters” column. Racine Daily Argus. Racine, Wisconsin. 9 November 1880. Page 3.
In Russian, “Салат Оливье.”
 New Larousse Gastronomique. Paris: Librairie Larousse. English edition 1977. Page 791.
 As accounted by Morozva, Nadezhda. 20 June 2009. Retrieved December 2009 from http://fotki.yandex.ru/users/nadezhdmorozova/view/178718?page=6