I find it usually doesnt work as advertised and you have to find the "Advanced mode" button (a strong candidate for the worst piece of UI ever) and then fiddle with several properties.

Here's probably the best reference:

http://blogs.msdn.com/b/robertbruckner/archive/2008/10/13/repeat-header-and-visible-fixed-header-table.aspx

Step 1) In the Tablix properties check the boxes for:

• Repeat header rows on each page.
• Keep header visible while scrolling.

Make sure that the Column Headers check boxes are NOT checked.

Step 2) In the Group pane on the left (Row Groups) the first line is Static (in Advanced mode).

• Set its: "ReapetOnNewPage" property to TRUE
• Set its: "FixedData" property to TRUE
• Set its: "KeepWithGroup" property to AFTER

I think what confuses people about these settings is that the "Row Headers" and "Column Headers" that the settings refer to are not visible if you have used a "table"-style tablix. These are only visible when using a "matrix"-style tablix.

Therefore I often see people trying to set this for tables and wondering why it does not work. As per the MSDN blog post referred to in Mike Honey's answer, if you have used a table then you have to fiddle about with the Advanced settings to get this to work.

My tip is to start with a matrix and make sure the row or column headers you want to remain visible are in the matrix row/column group areas (above and to the left of the double-dash lines). You can remove any row or column groups that you are not going to use. When you set the "remain visible" settings they should then just work as expected.

I couldn't find this property in Visual Studio, so I checked XML source.

1. In solution explorer right click on your report and View Code.
2. In xml code find:

<TablixRowHierarchy>
        <TablixMembers>
            <TablixMember>
                <TablixHeader>

1. Under <TablixMember> put this code:

<FixedData>true</FixedData>

Now save the code and you will see that header row is freezed.

Kindly note: We can keep the headers of a Tablix Freezed.

Work around:

1. We need to change the fixed data property to true of a header cell(static)
2. Remove the selection of check box for "keep the row or column header visible while scrolling"

Here in 2023 and this still is an issue. The accepted answer's link is broken now. Below is how you get this to work.

1. Click on the small down arrow to the right of the Column Groups and check Advanced Mode
2. Click on the (Static) row under the Row Group
3. On the properties area to the far right, Set the following:
4. FixedData = True, KeepWithGroup = After, RepeatOnNewPage = True
5. On the tablix header go into the properties and make sure the Keep header visible while scrolling is UNCHECKED for both the row header and column header sections.
6. Finally set the tablix header row BackgroudColor to white or something else, it is transparent by default. Without the background change the header text will float on of the data.