Then Melchizedek king of Salem brought out bread and wine. He was priest of God Most High, and he blessed Abram, saying, "Blessed be Abram by God Most High, Creator of heaven and earth. And praise be to God Most High, who delivered your enemies into your hand." Then Abram gave him a tenth of everything. (Gen. 14:18-20 NIV)
The LORD said unto my Lord, Sit thou at my right hand, until I make thine enemies thy footstool.
The LORD shall send the rod of thy strength out of Zion: rule thou in the midst of thine enemies.
Thy people shall be willing in the day of thy power, in the beauties of holiness from the womb of the morning: thou hast the dew of thy youth.
The LORD hath sworn, and will not repent, Thou art a priest for ever after the order of Melchizedek. (Psalm 110:1-4 KJV)
This "King Melchizedek of Salem, priest of the Most High God, met Abraham as he was returning from defeating the kings and blessed him"; and to him Abraham apportioned "one-tenth of everything." His name, in the first place, means "king of righteousness"; next he is also king of Salem, that is, "king of peace." Without father, without mother, without genealogy, having neither beginning of days nor end of life, but resembling the Son of God, he remains a priest forever. See how great he is! (Heb. 7:1-4a NRSV)
According to one common Jewish tradition, Melchizedek was Shem, son of Noah; 2 Enoch makes him Noah's nephew. Christians seem largely not to have been interested in these legends, although I'm told that Jerome somewhere mentions them. Philo interprets Melchizedek as a symbol of the Logos, which in a way we find in the book of Hebrews, as well, and the latter, of course, is the primary influence on what Christians have thought about him. The second thing that caught their attention was the bread and wine (in some modern translations bread and raisin-cakes), which has generally been read as a type of the Eucharist; Clement of Alexandria seems to be the first person to have discussed this explicitly:
Righteousness is peace of life and a well-conditioned state, to which the Lord dismissed her when He said, "Depart into peace." For Salem is, by interpretation, peace; of which our Saviour is enrolled King, as Moses says, Melchizedek king of Salem, priest of the most high God, who gave bread and wine, furnishing consecrated food for a type of the Eucharist. And Melchizedek is interpreted "righteous king;" and the name is a synonym for righteousness and peace.
Cyprian is a major influence on this line of thought in the West; from his Letter 62 to Caecilius:
Also in the priest Melchizedek we see prefigured the sacrament of the sacrifice of the Lord, according to what divine Scripture testifies, and says, "And Melchizedek, king of Salem, brought forth bread and wine." Now he was a priest of the most high God, and blessed Abraham. And that Melchizedek bore a type of Christ, the Holy Spirit declares in the Psalms, saying from the person of the Father to the Son: "Before the morning star I begot You; You are a priest for ever, after the order of Melchizedek; " which order is assuredly this coming from that sacrifice and thence descending; that Melchizedek was a priest of the most high God; that he offered wine and bread; that he blessed Abraham. For who is more a priest of the most high God than our Lord Jesus Christ, who offered a sacrifice to God the Father, and offered that very same thing which Melchizedek had offered, that is, bread and wine, to wit, His body and blood?