The problem of finding large average submatrices of a real-valued matrix arises in the exploratory analysis of data from a variety of disciplines, ranging from genomics to social sciences. This talk details several new results concerning the asymptotic behavior of large average submatrices of an nxn Gaussian random matrix. We begin by considering the average and joint distribution of the (globally optimal) kxk submatrix having largest average value. We then turn our attention to submatrices with dominant row and column sums, which arise as the local optima of a useful iterative search procedure for large average submatrices. Paralleling the result for global optima, we will consider the average and joint distribution of a typical (locally optimal) kxk submatrix with dominant row and column sums. The last part of the talk will be devoted to the analysis of the *number* of locally optimal kxk submatrices, $L_n(k)$, beginning with the asymptotic behavior of its mean and variance for fixed k and increasing n. Finally, we establish a central limit theorem for $L_n(k)$ that using Stein's method for normal approximation. Joint work with Shankar Bhamidi (UNC) and Partha S. Dey (Courant)