If you size your columns appropriately SSRS will do this for you. I usually have to work to have it not do this. I'm not sure if the page header will repeat or not, as I said, I usually try to get rid the columns breaking into two pages.
If the header doesn't repeat you could always try disabling it and recreate the header in the body of the report in a rectangle. Something like this:
[Rectangle1 with [Recangle2 with
Header stuff] headerstuff]
C1, C2, C3...C20 C21..C40, etc
Does that make sense? I don't envy you, even if what I did works for you, it's still going to be a major Pain to make this work. So what do the users do with this report? Do they print it out and lay the pages side by side to view the data?