I'm looking for a ressource similar to senate.gov, that gives the names of senators and their decision throughout United States history. The website above only goes back to the 101st congress (1989). Does such a source exist? How, if at all, were records kept in the early days of the republic (18th century)?
Yes, there is such a source. Congress is required under Article I, Section 5 of the Constitution to keep a journal of its proceedings, and it has done since 1789. For any votes before 1875, the House and Senate Journals stored on the Library of Congress site record roll-call votes. There is then a gap in the digitized media currently available until online versions of the Congressional Record after 1989. (see edit below) Keep in mind that the text of the Constitution requires that votes are recorded only "at the desire of one-fifth of those present," so there may not be an extant record of every single vote even today.
In response to your second question, the record of early Congresses is less extensive than the Congressional Record, which has since 1873 contained the text of remarks on the floor and statements entered by legislators "for the record." If you're interested in that text, however, the pre-1873 Journals are not the best sources. These were only ever the minutes of the legislative bodies without much additional context for what was said on the floor. A compendium of newspaper broadsheets compiled after 1834 known as the Annals of Congress is the best available (though sadly often incomplete) source for the text of 1789-1824 floor debates. From 1824-1837, it was the Register of Debates, which has been conveniently digitized by the Library of Congress. From 1837-1873, there's the Congressional Globe, which is not available in full online to my knowledge.
So if there are particular pieces of legislation you want to research, there's a great deal of compiled information available, just not necessarily items you can access from the comfort of home. You'd have better luck reaching out to your friendly neighborhood law librarian.
EDIT: I foolishly forgot about my go-to source for legislative history, govinfo.gov. You can indeed access the complete [Congressional Record](https://www.govinfo.gov/app/collection/crecb/_crecb/Volume%20001%20(1873) online! They're some huge PDFs, though.
You're looking for a publication called the Congressional Record if you want records of debate, and its predecessor the Congressional Globe. If you want votes its the House and Senate Journals. They are available at https://memory.loc.gov/ammem/amlaw/lwjrnl.html for inception to 1875, and http://leg.wa.gov/LIC/Pages/Floor-Journals.aspx for 1891- present.