To the extent available, Congressional debates are published in the Congressional Record back to 1873. For information on retrieving these debates see the "Congressional Record" entry.
Before then, summaries of selected debates were published the Annals of Congress (1798-1824), the Register of Debates in Congress (1824-1837) and the Congressional Globe (1833-1873). All three publications are available online on the Library of Congress' American Memory website. For more information about these publications, see An Overview of the Congressional Record and its Predecessor Publications by Richard J. McKinney.
Video: You may be able to find video of debates since 1987 in the C-Span Video Library.