Jean Valjean was sentenced according to the French Penal Code of 1810 (you can find an English translation here) which is often confused with the much more famous Code Napoleon; a law code which did not deal with criminal offenses.
The penal code contains the following:
Whoever has fraudulently abstracted a thing which does not belong to him, is guilty of theft.
and;
The penalty of death shall be inflicted upon the individuals guilty of theft, committed with the aggravation of all the five circumstances following:
1st. If the theft has been committed by night;
2d. If the theft has been committed by two or more persons;
3d. If the criminals, or any of them, were in possession of arms, apparent or concealed;
4th. If they have committed the crime;
Either by means of extend house-breaking (effraction exterieure), or of scaling, or of false keys, in a house, apartment, chamber, or lodgings, inhabited or used for habitation, or their appurtenances;
Or by assuming the title of a public functionary, or civil or military officer, or dressed in the uniform or costume of such functionary, or officer, or by alleging a false order of the civil or military authority.
5th. If they have committed the crime with violence, or threats of making use of their arms.
and;
The penalty of perpetual hard labour shall be inflicted upon every individual guilty of theft, committed by means of violence, and, moreover, with any two of the first four circumstances enumerated in the preceding article.
If the violence, with which the theft has been committed, has left marks of wounds or bruises, this circumstance alone shall suffice, that the penalty of perpetual hard labour shall be awarded.
Compare this to how Victor Hugo describes Valjeans crime:
One Sunday evening, Maubert Isabeau, the baker on the Church Square at Faverolles, was preparing to go to bed, when he heard a violent blow on the grated front of his shop. He arrived in time to see an arm passed through a hole made by a blow from a fist, through the grating and the glass. The arm seized a loaf of bread and carried it off. Isabeau ran out in haste; the robber fled at the full speed of his legs. Isabeau ran after him and stopped him. The thief had flung away the loaf, but his arm was still bleeding. It was Jean Valjean.
This took place in 1795. Jean Valjean was taken before the tribunals of the time for theft and breaking and entering an inhabited house at night. He had a gun which he used better than anyone else in the world, he was a bit of a poacher, and this injured his case.
(...)
Jean Valjean was pronounced guilty. The terms of the Code were explicit. There occur formidable hours in our civilization; there are moments when the penal laws decree a shipwreck. What an ominous minute is that in which society draws back and consummates the irreparable abandonment of a sentient being! Jean Valjean was condemned to five years in the galleys.
So by committing his crime in the first place and doing so by night (or rather in the evening, but it being considered night by the judge), Jean Valjean had already made sure he would be sentenced to hard labour.
Of course, he was not sentenced to 19 years (he initially got a 'mere' 5 years) but his escape attempts prolonged his sentence; as Hugo writes:
Towards the end of this fourth year Jean Valjean’s turn to escape arrived. His comrades assisted him, as is the custom in that sad place. He escaped. He wandered for two days in the fields at liberty, if being at liberty is to be hunted, to turn the head every instant, to quake at the slightest noise, to be afraid of everything,—of a smoking roof, of a passing man, of a barking dog, of a galloping horse, of a striking clock, of the day because one can see, of the night because one cannot see, of the highway, of the path, of a bush, of sleep. On the evening of the second day he was captured. He had neither eaten nor slept for thirty-six hours. The maritime tribunal condemned him, for this crime, to a prolongation of his term for three years, which made eight years. In the sixth year his turn to escape occurred again; he availed himself of it, but could not accomplish his flight fully. He was missing at roll-call. The cannon were fired, and at night the patrol found him hidden under the keel of a vessel in process of construction; he resisted the galley guards who seized him. Escape and rebellion. This case, provided for by a special code, was punished by an addition of five years, two of them in the double chain. Thirteen years. In the tenth year his turn came round again; he again profited by it; he succeeded no better. Three years for this fresh attempt. Sixteen years. Finally, I think it was during his thirteenth year, he made a last attempt, and only succeeded in getting retaken at the end of four hours of absence. Three years for those four hours. Nineteen years.
The case of Jean Valjean is of course also a social criticism by the author directed against that very justice system. Indeed, Victor Hugo claimed to have witnessed a starving young man being led away by police with a loaf of bread under his arm in 1846 as he was writing Les Miserables, which Hugo did not perceive as a sign of criminality but rather of hopeless poverty. Hugo himself makes it very clear that he considered the 19 year sentence to be absurd, writing:
In October, 1815, he was released; he had entered there in 1796, for having broken a pane of glass and taken a loaf of bread.
So in summary, yes hard labour was indeed a common punishment for theft in early 19th century France. Nevertheless, Jean Valjeans predicament (while possible) would have been an exceptional case.
Edit: By using the penal code of 1810, Hugo introduced an anachronism into the story. Had he used the contemporary French Penal Code of 1791, Valjean would have received 12 years "in irons" for the crime of theft/burglary alone
Based on the information about the crime given in these paragraphs:
One Sunday evening, Maubert Isabeau, the baker on the Church Square at Faverolles, was preparing to go to bed, when he heard a violent blow on the grated front of his shop. He arrived in time to see an arm passed through a hole made by a blow from a fist, through the grating and the glass. The arm seized a loaf of bread and carried it off. Isabeau ran out in haste; the robber fled at the full speed of his legs. Isabeau ran after him and stopped him. The thief had flung away the loaf, but his arm was still bleeding. It was Jean Valjean.
This took place in 1795. Jean Valjean was taken before the tribunals of the time for theft and breaking and entering an inhabited house at night. He had a gun which he used better than any one else in the world, he was a bit of a poacher, and this injured his case. There exists a legitimate prejudice against poachers.
With link to Hapgood's translation
The relevant law for determining his punishment would be the Code pénal, also known as the law of 25 September 1791.
Fortunately for Jean Valjean, this is a crime that seems to have been committed without violence against a person, which means he won't automatically be sentenced to 18 years minimum for the burglary. The relevant rule is article 6, section 2, title 2, part 2 of the code.
All other theft committed without violence against persons, with the aid of effraction, either by the thief, or by his accomplice, will be punished by eight years of irons.
Anyone sentenced to the punishment of "irons" will (as is explained in article 6, title 1, part 1 of the Code)
be employed at forced labour for the profit of the state, either in the interior of a "maison de force", or in ports and arsenals, or for the extraction of mines, or for the drying of marshes, or for any other difficult work, which, at the demand of the departements, can be determined by the legislative body.
Article 7 makes the situation even worse for Valjean. The article lists five circumstances that will increase the punishment by two years for every circumstance that applies.
The first, if the effraction is done to doors or exterior closures of buildings, houses or edifices;
As opposed to "effraction" that consists of e.g. breaking into a chest or a locked room of a house that you're already inside. A window is included in the category "exterior closures", and Valjean did break one to gain access to the interior of a house. So, this article means that Valjean is now sentenced to 10 years instead of 8.
The second, if the crime is committed in a house currently inhabited or serving as habitation;
This building is probably uninhabited for the purposes of this article, so the sentence is still 10 years of irons.
The third, if the crime is committed at night;
This is the case for Valjean's theft, so the sentence is now 12 years.
The fourth, if it was committed by two or multiple people;
Not applicable. So, still 12.
The fifth, if the guilty person or persons were carrying firearms or any lethal weapon.
We're told that the gun was an aggravating factor, which means he must have had the gun with him while the crime was committed. This brings the sentence up to a total of 14 years of forced labour.
The biggest problem for Valjean is the burglary, not the theft. If he hadn't broken anything to get to the bread, the punishment according to article 16 of the same section would have been 6 years of irons, plus 2 for night crime (art. 18). If he hadn't entered a building, but still had a gun with him, it would have been four years of prison (article 22) plus 2 for night crime (art. 24).
If he hadn't had a gun, and hadn't entered or broken into a building, the punishment according to article 28 would be punished by "police correctionnelle". Punishment in the winter of 1795 has three tiers, defined in article 599-603 of the Code des délits et des peines (also known as the law of 3 Brumaire year IV, passed in October 1795). The lowest tier is "simple police" for the least serious type of offense, punishable by up to 3 days in prison or a fine worth three days of labour. The second is "peines correctionnelles", which is everything between the "simple police" and the highest tier, which is two categories; "peines afflictives" and "peines infamantes". Theft in the middle tier is punished by up to 2 years in prison (or four in cases of recidivism) according to the law of 19 July 1791. No extra time for night crime.
So the original punishment of five years that Hugo gives Valjean actually seems a lot milder than what would have been the actual law at the time. He would probably have been given 14 years of hard labour instead of 5, if all of the aggravating circumstances in the narration were accepted by the jurors.
As for his many escapes, the law of 12 October 1791 punished escapees with three years of forced labour. Interestingly, this only applies to those who escape from forced labour, since the "forçats" are punished under maritime law; escaping from a prison wasn't illegal unless crimes were committed on the way out (Morin, 1842, p. 305-306). Three extra years was the rule until November 1806 (Chauveau, 1843, p. 263) which means that Jean Valjean's first escape four years into his sentence (ca. 1800) would have resulted in a total sentence of 17 years. In the sixth year, he escaped again and resisted his captors. I haven't been able to find the special decree Hugo mentions, but Valjean would still in 1802 have been sentenced to a minimum three years, meaning his sentence would be 20 years at least. In the tenth year (1806), he escaped again. If this happened before November, the case is as before. If it is after November, his sentence would be lengthened by 24 years. So now the total is either 23, or 44. For the escape in his thirteenth year, the punishment would definitely have been 24 years. His final sentence would be either 47 or 68 years.
Sources:
Link to the text of the law of 19 July 1791
Link to the text of the law of 25 September 1791, AKA the code pénal of 1791
Link to the text of the law of 3 Brumaire year 4, AKA the code des délits et des peines of 1795
Chauveau, Adolphe (1843) Théorie du code pénal vol. 1
Morin, Pierre Achille (1842) Dictionnaire du droit criminel.