The Sullivan shows exist as video from 1959 onward. The first is from 1/18/59. Everything previous to that is preserved as kinescopes. The first 6 months of Ed's show are (visually) totally lost, as they pre-date CBS's ability to kinescope their programming.
And what Steve H. said is correct-- we don't see it too often, but there's a surprising amount of early videotape that's been preserved. As I mentioned in the color tape thread, you might want to look here:
http://www.cinema.ucla.edu/collections/allTV.html
for some examples.
-Kevin