A martyr is someone who dies for their faith. Originally in the early Christian church, only a martyr could be a saint. Once Christianity became the dominant religion, however, it became much harder to die for one's faith, and "confessor" saints became the norm, people who "confessed" their religiosity through the holiness of their life and the miracles they worked (especially after death).
Interestingly, in the US after 911 "martyr" has become a pejorative term. Those who crashed planes into the World Trade Center claimed they were willing to die for Islam. (Many Muslims point out that this sure doesn't look like the faith they know, but that's a separate issue.) Thus "martyr" and "terrorist" have been linked for many in the twenty-first century. But in the Middle Ages martyrs were greatly admired.
The New Testament itself tells the story of Saint Stephen "protomartyr" (i.e. first martyr), put to death for believing in Christ. Many churches in the West were dedicated to him, starting in the fifth century.
The West had very few saints before the sixth century, but in the sixth century a great many bones of early martyrs were discovered. These people, it was universally agreed, had died while trying to convert the pagans of the Roman Empire, or else had been rounded up and put to death by pagan emperors like Nero or Diocletian. The catacombs of Rome were full of bones, and the Christians were sure that a great many of these were the bones of Christian martyrs put to death in the Coliseum.
Elaborate accounts of the lives and deaths of those who had first brought Christianity to the provinces of the Empire were put together. The city of Lyon traditionally had 177 martyrs, all supposedly put to death for their faith in the second century. Attempts were made to name them all, though some of their names, like "Rhône River" or "Mature," seem at best odd. Other missionaries to the pagans were sent out from Lyon, including Marcellus and Benignus, who in essence had a saint-off contest--they headed north, one on either side of the river, to see who could be martyred first (Marcellus won, or lost depending on your point of view).
By the late sixth century, elaborate explanations were being given for why the martyrs of the second and third centuries were forgotten for a few centuries, only to be rediscovered in the fifth or sixth. The 177 martyrs of Lyon, for example, were said to have been burned and their ashes thrown in the river--though by the end of the sixth century a church in Lyon would tell anyone interested that it had those ashes, and indeed had had them all the time, since Christians (apparently too timid to be martyred themselves) had secretly pulled them from the river and buried them suitably.
It is easy to doubt the historicity of most of the West's martyr-saints, even though most western dioceses had a (supposed) martyr for their first bishop. By the fifth and sixth centuries, with religious persecution far in the past, the West instead started producing historically verifiable confessor saints.
Martyrdom was still preferred, however. Someone practicing extreme asceticism (living in the desert alone, eating almost nothing) was described as almost like a martyr. Those who left the ordinary world for the monastery were said to be practicing a "bloodless martyrdom." A priest or monk who was killed by a layman was presumed to be a martyr, though he would still need some good posthumous miracles for real proof.
When knights headed off on Crusade, starting at the end of the eleventh century, it was suggested that they might wear the crown of martyrdom if they died in the Holy Land. However, dying of disease or shipwreck (as many did who did not make it back) was hard to construe as martyrdom, and even those killed in battle with Muslims didn't look all that saintly to those who might otherwise have declared them saints.