Is this a submatrix?
Pyth, 10 bytes

}CQsyMCMyE


Test suite

This is fairly straightforward. First, we consider B as a list of rows, and take all subsets using yE. Then, each of those matrices is transposed with CM, and all subsets are taken of their rows, with yM. Concatenating these sublists with s gives all possible transposed submatrices. So we transpose A with CQ, and check if it is present with }.