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 }.

Dyalog APL, 53 43 bytes

(⊂A)∊⊃∘.{∧/∊2</¨⍺⍵:B[⍺;⍵]⋄⍬}/⍳¨(⍴A←⎕)/¨⍴B←⎕

B←⎕, A←⎕prompt for B and A
⍴B, ⍴A dimensions of B and A
/¨ replicate each, e.g. 2 3/¨4 5 → (4 4) (5 5 5)
⍳¨ all indices in each of the coordinate systems with those dimensions
∘.{…}/ table of possible submatrices, where each submatrix is defined as the result of the anonymous function {…} applied between a pair of coordinates ⍺ and ⍵
∧/∊2</¨: if both ⍺ and ⍵ are (∧/∊) both (¨) increasing (2</), then...
B[⍺;⍵] return submatrix of B created from the intersections of rows ⍺ and columns ⍵
⋄⍬ else, return an empty vector (something that A is not identical to)
(⊂A)∊⊃ check if the whole of A (⊂A) is a member of ∊ any of the submatrices (⊃)

---

Old 53-byte solution:

{(⊂⍺)∊v∘.⌿h/¨⊂⍵⊣v h←(⍴⍺){↓⍉⍺{⍵/⍨⍺=+⌿⍵}(⍵/2)⊤⍳⍵*2}¨⍴⍵}

{…} an anonymous inline function, where ⍺ is left argument and ⍵ is right argument
⍴ shape, e.g. 2 3 for a 2-by-3 matrix
(⍴⍺){…}¨⍴⍵ for each pair of corresponding dimension-lengths, apply this anonymous function
⍳⍵*2 indices of the square of, i.e. 2 → 1 2 3 4
(⍵/2)⊤ convert to binary (number of bits is dimension-length squared)
{⍵/⍨⍺=+⌿⍵} of the binary table, select the columns (⍵/⍨) where the number of 1s (+⌿⍵) is equal to the the length of that dimension in the potential submatrix (⍺=)
↓⍉ make table into list of columns
v h← store as v(ertical masks) and h(horizontal masks)
⊣ then
h/¨⊂⍵ apply each horizontal mask to the right argument matrix
v∘.⌿ apply each vertical mask each one of the horizontally masked versions of the large matrix
(⊂⍺)∊ check if the left argument matrix is member thereof

Jelly, 12 10 bytes

Thanks @Dennis for -2 bytes

ZŒP
ÇÇ€;/i

Nearly the same algorithm as @isaacg, except we transpose the matrix before taking subsets.

ZŒP      Helper link. Input: z
Z          Transpose z
ZŒP        All subsets of columns of z.

ÇÇ€;/i   Main link. Input: B, A. B is a list of rows.
Ç          Call the helper link on B. This is the subsequences of columns of A.
 ǀ        Call the helper link on each column-subsequence.
           Now we have a list of lists of submatrices of B.
   ;/      Flatten that once. The list of submatrices of B.
     i     then get the 1-based index of A in that list.
           If A is not in the list, returns 0.

Try it here.