Frigo's cache-oblivious algorithms paper
The version of the paper I am reading does not contain that statement on page 3 that you quote, "An $s \times s$ submatrix is stored in $\Theta(s+s^2/B)$ cache lines." However, it does state that the authors are going to consider matrix multiplication in the case the matrix is stored in row-major order.

In that layout, matrix location $(i,j)$ is stored at memory location $m*i + j$, where $m$ is the number of columns in the matrix. If $m \geq B$ where $B$ is the cache line size, successive rows of an $s \times s$ submatrix will occupy distinct cache lines.

As such, there are at least $s$ lines occupied. As you noted, there are at least $s^2/B$ cache lines occupied, since there are $s^2$ elements and only $B$ fit in a cache line. So, the value is $\Theta(\max(s, s^2/B))$ when $m \geq B$, and in Landau notation, maximum and sum are interchangeable.