The scriptures first mention Melchizedek in Genesis 14, which describes him as "king of Salem" and "priest of the most high God." After Abraham (or, more accurately, Abram, since this is before his name change) retrieves the people and goods that raiders had stolen from Sodom, Melchizedek shows up to bless the patriarch, and offer him bread and wine. Abram then gives him a tenth of the spoils, which is used as a model for the system of tithing. The next mention of the priestly king is in Psalm 110, in which the narrator calls the person he's addressing "a priest for ever after the order of Melchizedek." The New Testament adds more to the story of this man, saying in Hebrews 7, "This Melchizedek was king of Salem and priest of God Most High. He met Abraham returning from the defeat of the kings and blessed him, and Abraham gave him a tenth of everything. First, his name means 'king of righteousness'; then also, 'king of Salem' means "king of peace." Without father or mother, without genealogy, without beginning of days or end of life, like the Son of God he remains a priest forever." So Melchizedek is immortal and has no parents? That seems like it would have been worth mentioning somewhere else in the Bible, doesn't it? Some take this to mean that it was the priesthood itself, rather than Melchizedek himself, that was supposed to last forever. It's quite likely, however, that the author of Hebrews was referring to a then-popular tradition regarding the King of Salem. The book of 2 Enoch, which was quite likely written around the same time, states that he was born of a virgin who had just died, and was fully grown from birth. Other stories say he was born circumcised. Rabbis often identified Melchizedek with Noah's son Shem, and later takes on the character make him an alternate identity of the Archangel Michael.
So where is this Salem that Melchizedek is said to have ruled? Well, as the passage from Hebrews suggests, some think it was just a metaphorical reference to his being king of peace, or of the upper world. But others think it was an early name for the city of Jerusalem, and I've seen it suggested that the Northern Kingdom had a similar tradition of Salem being Shechem on Mount Gerizim. And was Melchizedek actually a priest of Yahweh back in the time of Abraham, long before the Jewish priesthood had been established? That seems to be the commonly accepted interpretation, but it has also been proposed that the "El Elyon" referred to in the Genesis passage was actually a different god.