To quote from The Independent about the source of mind palaces:
As it turns out, memory palaces like Holmes’ are a real thing, and
have been for thousands of years. It all began with a lucky escape
from a collapsing banquet hall by the Ancient Greek poet Simonides,
who realised that by visualizing the room where the accident happened,
he could perfectly recall the names of all his squashed fellow
revellers. He later found a less morbid use for this discovery, by
associating things he wanted to remember with walks through buildings
he knew well.
The article goes on to describe how many mental athletes around the world use this technique to compete in memory championships, before interviewing a collection of these athletes.
Finally, to use the article's rather lovely conclusion as to why a palace could be useful:
In fact, the ‘Sherlock’ series 3 finale hinted at the prestige
knowledge can have in the digitized world: sometimes the only truly
safe place to keep information is your own brain. Also, knowing the
number for a cab company is very helpful at 3am when your phone is
dead. Long live the mind palace.
For more information, you can look up the Method of loci, which is what the memory palace is more traditionally known as. To quote from the Wiki:
'The method of loci', an imaginal technique known to the ancient
Greeks and Romans and described by Yates (1966) in her book The Art of
Memory as well as by Luria (1969). In this technique the subject
memorizes the layout of some building, or the arrangement of shops on
a street, or any geographical entity which is composed of a number of
discrete loci. When desiring to remember a set of items the subject
literally 'walks' through these loci and commits an item to each one
by forming an image between the item and any distinguishing feature of
that locus. Retrieval of items is achieved by 'walking' through the
loci, allowing the latter to activate the desired items. The efficacy
of this technique has been well established as is the minimal
interference seen with its use.
The page also has an interesting collection of movies and television shows where the technique has been used.
As for learning it yourself? Try this article from Remember Everything