Why does Himura always end almost every sentence with gozaru in this show? Is this normal for people in that time period?
～ござる is commonly known as a more polite way of ending a sentence, but it's also common in historical dramas because it is a bit archaic-sounding. ANN has an entry on this in their lexicon here. A more detailed analysis of Kenshin's speech patterns can be found here.
EDIT: It was pointed out in chat that there's a closely related question with a really good answer on the Japanese Stack Exchange.
Why does Himura always end almost every sentence with gozaru in this show?
To express his self-abasement, modesty, and serving attitude. This is the persona he adopted in the Meiji era as a rurouni (wandering samurai).
Kenshin's usage of this speech pattern is not for the intent of marking the series as historical fiction. This is evidenced by the fact that none of the other characters in the series speak this way.
Furthermore, Kenshin did not use「でござる」(de gozaru) when he was younger (before his rurouni phase of life), and when he flips into hitokiri battousai mode within the series proper (when his eyes are yellow), he does not use this copula verb form because, in battousai mode, he does not have a meek personality.
The stark difference between his speech patterns and everyone else's emphasizes Kenshin's personal, intentional choice to use this style of speech. Rather than the mangaka, Nobuhiro Watsuki, intending this phrasing to be representative of the era, it highlights Kenshin's now humble personality and that he is a bit different from the new norms of his time period (in the same way that he persists in carrying a sword and sheath, still wears hakama rather than pants, etc.).
"De gozaru" is part of Kenshin's response to realizing that he was very mistaken in his previous actions and convictions during the Bakumatsu period. In combination, he also uses 「拙者」 (sessha), which is a 謙譲語 (kenjougo = humble language) word. Kenjougo is a lowering of the speaker in comparison to the person/people being spoken to. As seen in thejapanesepage.com's article on keigo (polite speech), kenjougo is (to this day) employed in
referring to oneself or one's family members and (usually) speaking to someone higher up in social rank, position or some other criteria for determining status. However even some people with high positions may choose to use the humble form with those under him/her.
As Kenneth Hanson explains
A copula is a word meaning “to be”, and is used to predicate a sentence. . . . The copula takes three basic forms in standard speech: the plain form だ (da) in informal speech, the polite form です (desu) in formal speech, and でございます (de gozaimasu) in honorific speech. In the case of the last form, the same word is used both for respectful and humble speech; unlike other components of keigo, de gozaimasu is neutral to who the subject is. . . . In truth, things are a little more complicated than this. . . . de gozaru is the honorific form of de aru, but with keigo the polite form of an honorific verb is almost always used, so we get de gozaimasu.
Is this normal for people in that time period?
No. It was not customary for people to use 「でござる」 in this period. Rurouni Kenshin takes place starting in 1878 (year 11 of the Meiji era) and the epilogue ends in the spring of 1885 (Meiji Era year 18). The side story Yahiko no Sakabatou takes place 5 years after the Great Kyoto Fire.
the stereotypical Samurai speech in Jidaigeki is actually based on the Edo dialect of late Edo period. Many of the mannerisms you'd find in this speech do not specifically represent Samurai, but rather a typical resident of Edo in that particular time.
The Edo era lasted from 1603 to 1868; however, Japan had been forcibly opened to the outside world by Commodore Matthew C. Perry’s black ships back in 1853 (15 years before Edo officially ended). The Convention of Kanagawa was signed with Perry in 1854, with three more international treaties of Amity and Commerce following in 1858 (the shogunate was successfully disbanded in 1867, the Boshin civil war raged for over a year as loyalists attempted to restore the shogunate to power, and the Republic of Ezo, a secessionist state located in what is now Hokkaido prefecture, stayed afloat for half of 1869 before being crushed by Japan’s imperial forces).
In contrast to speech patterns of the late Edo period, Meiji is when Japan's first generation of young men attended college, learned English, learned how to eat with fork and spoon, and went to study abroad. Japan was very keen to portray itself as rapidly modernizing so as not to be colonized by other nations (approximately when Perry opened Japan to the West, the British Empire took control of India; America annexed Alaska and Hawaii; and the Berlin Conference of 1884 set the Scramble for Africa into motion. Historical figure Nitobe Inazo explained that "[t]he Union Jack was firmly planted in India and was moving eastward to Singapore, Hong-Kong, and there was some probability of it marching on to China. Why not to Japan too? The French Tricolor was also seen floating over Cambodia, Annam, and Tonkin, and nobody could tell how far north or east it would fly. More alarming than these, the Muscovite Power, like a huge avalanche, was steadily descending southwards from its Siberian steppes, crushing everything on its way." Inazo Nitobe, “Lectures on Japan: The Manchurian Question and Sino-Japanese Relations,” in Lectures on Japan: An Outline of the Development of the Japanese People and Their Culture, pp. 227–29).