Messiah (mâšîah, "the anointed one"): Jewish religious concept, a future savior who will, in some sense, come to restore Israel. The nature of both the Messiah and the restoration was a matter of debate, and there were several claimants.
Jewish and Christian texts describing the rise of Islam, state that Muhammad announced the coming of the Messiah. These sources are older than the oldest Islamic written traditions and may contain accurate historical information, although it is possible - perhaps even likely - that their authors misunderstood the teachings of Muhammad. An example is the Doctrina Jacobi, a Christian text written in or about 640 CE. The text has a very strong Anti-semitic character. It describes a Jewish discussion set in 634, in which a letter by a Palestinian Jew with the name Abraham is read.
We Jews are full of joy. They say that a prophet has appeared among the Saracens, and that he proclaims the advent of the anointed one, the Messiah who is to come. When I, Abraham, had gone to Sykamina, I consulted an old man well-versed in the Scriptures on this matter, asking: "What is your opinion, my master and teacher, on this prophet who has appeared among the Saracens?"
With a mighty sigh, he replied: "He is an impostor. Prophets don't come with sword and chariot. Truly the events of today are the works of disorder. I fear that the Messiah that came first, the one that is worshipped by the Christians, was indeed sent by God, and that we will be found by the Devil. Didn't Isaiah say that we, Jews, 'are to have a heart of stone full of errors until the end of the world'? But go now, master Abraham, and find out for yourself about this prophet."
Searching and toiling, I, Abraham, was learned from people who had met him: "You won't find any truth in this prophet, only bloodshed; for he says he possesses the keys of paradise, which is incredible." (Doctrina Jacobi 5.16)
It is impossible to establish the historical truth of this story. Maybe Muhammad considered himself the Messiah, or just presented himself as the Messiah in order to be accepted by the Jews, or was thought to have claimed to be the Messiah by the author of this text.
One (not completely convincing) indication that he made, at some stage of his career, some messianic claim can be found in the remark quoted above, that Muhammad said that he possessed the keys of paradise; this cannot be a Christian invention, because Christians believed Peter held these keys. Moreover, this motif is present in some very old Islamic traditions, where it is treated as a harmless metaphor - which may or may not be a way to neutralize a potentially embarrassing piece of information.
It may be noted that according to an old tradition, Muhammad was recognized by a Syrian monk as the Shiloh, a mysterious figure mentioned in Genesis 49 that was identified with the Messiah (go here for discussion).