In 1267, a man named Roger Godberd (who had been outlawed for fighting against the King during the Second Barons' War) took up residence in the Forest of Sherwood, along with a number of other outlaws of whom he was apparently the leader. He was caught and imprisoned by the Sheriff of Nottingham, but escaped; the Sheriff pursued him for several years, including laying siege to a castle in which he and the other outlaws were being protected. (The lord of the castle did ultimately surrender, but not before helping Godberd sneak out to safety.) Godberd was ultimately captured again, shortly before the new King, Edward III, returned from crusade and issued him a pardon.
If this story sounds overwhelmingly familiar, that's likely partly a coincidence, as records of Robin Hood first appear nearly forty years before Godberd's outlawry. But it does seem possible, or even likely, that the similarities between Godberd and the earlier stories of Hereward the Wake (a few of which were later recycled into Robin Hood tales) may have shaped the form of the narrative with which we are familiar today.
The idea of the noble outlaw in English legend, in other words, did not begin with a single historical figure. Hereward the Wake, who deserves his own post at some point in the future, was in exile well before his rebellion, when he apparently became a leader of Saxon resistance against the Normans in 1070. It's not entirely clear whether he was a real person; like Robin Hood, there are primary sources attesting to his existence, but none that are entirely reliable.
"Robin Hood" (and various other spellings) appears in English court records from the 1220s, as a defendant in cases all over England. It appears the name was a stock legal pseudonym for defendants, much like charging a "John Doe" today, which later evolved into the name of a character to whom many legendary stories are attributed. The use of a name which might have been equivalent to "John Doe" also suggests that the first compilers of the stories wished to present him as an everyman, albeit one who has been forced into outlawry; this is probably part of how he comes to be seen as the hero even in stories of his criminal exploits.
It's likely that several historical people from the high medieval period influenced the legends; quite a few have been reported, and there's no reason to assume only one of these hypotheses is correct. Regardless, no historian currently working on the problem believes the legends are especially accurate; rather, various real people are suggested as individuals on whose memory various fanciful stories have been hung. None of these individuals, however, would have been supporters of King Richard I during his Crusade, as is often suggested.
In most of the early stories, Robin Hood is a heroic rogue, but the notion that his heroism comes from concern for the people and that he is anything other than a predatory criminal is a much later notion - there is, in fact, no reference to Robin Hood robbing from the rich to give to the poor until ca. 1800! Rather, he is presented as a yeoman (definitely not a lord, though he is portrayed as such in a few sources beginning in the late 16th century) who is outlawed, lives in the woods (most typically Sherwood Forest, living as a poacher), periodically steals things, gets into fights, outwits opponents, and is very devoted in practicing his Christian faith.
By the late 14th century, ballads of Robin Hood's exploits were popular, though the first examples that still survive are a hundred years younger than that. Regardless, as ballads became popular, Robin Hood ballads were one of the first and most successful genres; they make up the bulk of the earliest ballads collected by Child, and it has been estimated that more songs have been written in the English language about Robin Hood than about any other character save God.
Through these ballads, we can get a very clear sense of the late medieval conception of Robin Hood; the 15th-century "Gest of Robyn Hode" is especially valuable, as it appears to be a series of earlier forgotten poems tied together into one monstrously-long whole. Robin's companions, who would later come to be known as the "Merry Men," were said to be quite numerous (sometimes there are over a hundred of them, consistent with a small military force for a rebellious commander whether in 1070 or 1265), but only a few individuals are introduced in these sources. The first three seem to have been Little John, Much the Miller's Son, and Will Scarlet. Little John in particular is mentioned in prose sources as early as 1420.
Another tradition that arose by the late 15th century was the introduction of Robin Hood as a character at May Day festivals. It is likely that he first appeared in these festivals as part of short plays based on his adventures, but as his popularity grew he started to appear directly integrated into other parts of the entertainment; Cecil Sharp cites a depiction of a team of morris dancers dressed as Robin Hood and some of his companions, for example.
It is at these fairs that Robin Hood was first brought into contact with another of their most popular characters: Maid Marian, a comic figure typically portrayed by a bearded man in drag. (The "betty", or obviously-male dancer in drag accompanying the performance in northern English sword dances, was still sometimes identified with Maid Marian as late as the early twentieth century.) The first appearances of Maid Marian date back to the 13th century (and unlike Robin Hood she is a Continental import, originating in France), but she is not connected with Robin Hood until ca. 1500. However, as the popularity of the two characters brought them into the same performances with increasing frequency, it became standard to identify the two as love interests for one another, to the potentially rather lewd delight of the audience. While Marian is now a more fully feminine character (and often a virginal one, as in those stories which have her leaving a convent to be with Robin), and often made more passive than in the Renaissance, she remains Robin Hood's love interest to the present day. In early sources which connect the two, Marian is presented as a capable heroine in her own right; in one story, for example, she defeats Robin in a sword fight. Her status being reduced to gaining relevance only because of her love for the male hero is a product of the Victorian era, when many Robin Hood stories were revived and retold in forms more familiar to the modern reader.
In short, our modern concept of Robin Hood is a 19th-century retelling of popular entertainments in many media (prose, verse, theater, and even dance) from 16th-century England, which arose in the context of seasonal springtime festivals and are in turn based on earlier folktales with influence from an unrelated tradition; these stories may or may not be rooted in the life of a historical figure (or more likely several), and are definitely related to a tradition from as early as the late eleventh century. Even to this day, the notion of the heroic rogue, who may or may not be giving to the poor but is certainly robbing from the rich and evading the authorities, is a popular one; not only do we continue to tell stories of Robin Hood, but we also bring back the motif in a modern context under other names - but whether we call him Nathan Ford, Daniel Ocean, or Henry Gondorff, the roguish leader of a band of people that live outside the law is always an echo of ideas we see in the earliest tales of Robin Hood.