The OED gives maybe as a adverb, noun and adjective. It is most likely to occur at the beginning of a sentence as an adverb.
The etymology is given as
Etymology: Shortened < it may be < it pron. + may v.1 + be v. and can also occur with a subordinate clause, and as a noun.
Maybe was uncommon in English before the mid-19th century when it was considered poetic or dialect. Its origins can be seen in the hyphenated form.
1825 J. Jennings "Observations on the Dialects of West England". May-be, mâ-be, perhaps; for which one of these words is almost invariably used.
1829 J. Hunter "Hallamshire Glossary". May-be. This is at least as good as the hybrid word perhaps, by which it has been supplanted.
As an adverb at the beginning of a sentence - "Maybe I will visit her tomorrow" - it is almost always a free modifier, i.e. it modifies the whole of [what appears to be] the main clause.
As far as
Probably I will. Is not-so allowed.
is concerned. I cannot put it better than Jack O'Flaherty above:
(I don't agree that Probably I will. is impossible, though it's less likely than I probably will.)