Some things are not as they seem.  Like in the Tablix (data table) properties there’s a setting that says “Repeat header rows on each page.”  Checking this does not repeat the header rows on each page.

TablixProperties

I found some information elsewhere that says you also have to:

1. In the grouping pane, Go to advanced mode
(click on the small black down arrow on the far right of the grouping pane.  A bunch of bars that say Static will show up.)

AdvancedModeStatic

2. Select the corresponding (Static) item in the row group hierarchy.  (not the ones in the Column Groups side.  For me it was the first one in the Row Groups)
3. In the properties grid, set RepeatOnNewPage to true

Properties
4. KeepwithGroup to After
5. FixedData to True

After doing this my row headers started showing up on all pages.  A lot of work for something that seems like should have been taken care of by the first setting.