How can I get all 4 × 4 submatrices of an n × n matrix?

You can use Subsets:

mat = Array[Subscript[a, ##]&, {6, 6}];

TeXForm @ MatrixForm @ mat

$\left( \begin{array}{cccccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} & a_{1,6} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,1} & a_{6,2} & a_{6,3} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right)$

fourbyfours =  mat[[#, #]] & /@ Subsets[Range[6], {4}];

TeXForm[Grid @ Partition[MatrixForm /@ fourbyfours, 3]]

$\tiny\begin{array}{ccc} \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,5} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,5} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,5} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,6} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,6} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,6} \\ a_{6,1} & a_{6,2} & a_{6,3} & a_{6,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,4} & a_{1,5} \\ a_{2,1} & a_{2,2} & a_{2,4} & a_{2,5} \\ a_{4,1} & a_{4,2} & a_{4,4} & a_{4,5} \\ a_{5,1} & a_{5,2} & a_{5,4} & a_{5,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,4} & a_{1,6} \\ a_{2,1} & a_{2,2} & a_{2,4} & a_{2,6} \\ a_{4,1} & a_{4,2} & a_{4,4} & a_{4,6} \\ a_{6,1} & a_{6,2} & a_{6,4} & a_{6,6} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,5} & a_{1,6} \\ a_{2,1} & a_{2,2} & a_{2,5} & a_{2,6} \\ a_{5,1} & a_{5,2} & a_{5,5} & a_{5,6} \\ a_{6,1} & a_{6,2} & a_{6,5} & a_{6,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{1,1} & a_{1,3} & a_{1,4} & a_{1,5} \\ a_{3,1} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,1} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,1} & a_{5,3} & a_{5,4} & a_{5,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,3} & a_{1,4} & a_{1,6} \\ a_{3,1} & a_{3,3} & a_{3,4} & a_{3,6} \\ a_{4,1} & a_{4,3} & a_{4,4} & a_{4,6} \\ a_{6,1} & a_{6,3} & a_{6,4} & a_{6,6} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,1} & a_{1,3} & a_{1,5} & a_{1,6} \\ a_{3,1} & a_{3,3} & a_{3,5} & a_{3,6} \\ a_{5,1} & a_{5,3} & a_{5,5} & a_{5,6} \\ a_{6,1} & a_{6,3} & a_{6,5} & a_{6,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{1,1} & a_{1,4} & a_{1,5} & a_{1,6} \\ a_{4,1} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,1} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,1} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{2,2} & a_{2,3} & a_{2,4} & a_{2,6} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,6} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,6} \\ a_{6,2} & a_{6,3} & a_{6,4} & a_{6,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{2,2} & a_{2,3} & a_{2,5} & a_{2,6} \\ a_{3,2} & a_{3,3} & a_{3,5} & a_{3,6} \\ a_{5,2} & a_{5,3} & a_{5,5} & a_{5,6} \\ a_{6,2} & a_{6,3} & a_{6,5} & a_{6,6} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{2,2} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{4,2} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,2} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,2} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,3} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right) \\ \end{array}$

Alternatively, you can use Minors:

pminors = Diagonal @ Minors[mat, 4, Identity];
pminors == fourbyfours

True

If you want submatrices with consecutive indices:

fourbyfoursconsec = Join @@ Partition[mat, {4, 4}, {1, 1}];
Length@fourbyfoursconsec

9

TeXForm[Grid[Partition[MatrixForm /@ fourbyfoursconsec, 3]]]

$\tiny\begin{array}{ccc} \left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} \\ a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{1,3} & a_{1,4} & a_{1,5} & a_{1,6} \\ a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ \end{array} \right) \\ \left( \begin{array}{cccc} a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} \\ a_{6,1} & a_{6,2} & a_{6,3} & a_{6,4} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \\ a_{6,2} & a_{6,3} & a_{6,4} & a_{6,5} \\ \end{array} \right) & \left( \begin{array}{cccc} a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,3} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right) \\ \end{array}$

mat = Array[a, {6, 6}];

Join @@ Table[mat[[j ;; j + 3, k ;; k + 3]], {j, Length@mat - 3}, {k, Length@mat - 3}]

$\left\{\left( \begin{array}{cccc} a_{1,1} & a_{1,2} & a_{1,3} & a_{1,4} \\ a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ \end{array} \right),\left( \begin{array}{cccc} a_{1,2} & a_{1,3} & a_{1,4} & a_{1,5} \\ a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ \end{array} \right),\left( \begin{array}{cccc} a_{1,3} & a_{1,4} & a_{1,5} & a_{1,6} \\ a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ \end{array} \right),\left( \begin{array}{cccc} a_{2,1} & a_{2,2} & a_{2,3} & a_{2,4} \\ a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} \\ \end{array} \right),\left( \begin{array}{cccc} a_{2,2} & a_{2,3} & a_{2,4} & a_{2,5} \\ a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \\ \end{array} \right),\left( \begin{array}{cccc} a_{2,3} & a_{2,4} & a_{2,5} & a_{2,6} \\ a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ \end{array} \right),\left( \begin{array}{cccc} a_{3,1} & a_{3,2} & a_{3,3} & a_{3,4} \\ a_{4,1} & a_{4,2} & a_{4,3} & a_{4,4} \\ a_{5,1} & a_{5,2} & a_{5,3} & a_{5,4} \\ a_{6,1} & a_{6,2} & a_{6,3} & a_{6,4} \\ \end{array} \right),\left( \begin{array}{cccc} a_{3,2} & a_{3,3} & a_{3,4} & a_{3,5} \\ a_{4,2} & a_{4,3} & a_{4,4} & a_{4,5} \\ a_{5,2} & a_{5,3} & a_{5,4} & a_{5,5} \\ a_{6,2} & a_{6,3} & a_{6,4} & a_{6,5} \\ \end{array} \right),\left( \begin{array}{cccc} a_{3,3} & a_{3,4} & a_{3,5} & a_{3,6} \\ a_{4,3} & a_{4,4} & a_{4,5} & a_{4,6} \\ a_{5,3} & a_{5,4} & a_{5,5} & a_{5,6} \\ a_{6,3} & a_{6,4} & a_{6,5} & a_{6,6} \\ \end{array} \right)\right\}$

Might not be so elegant, but try this:

(* create a test array *)
startingArray = ArrayReshape[Range[36], {6, 6}];
startingArray // MatrixForm
all4x4 = Partition[Partition[#, 4, 1] & /@ startingArray, 4, 1];
MatrixForm[#] & /@ Flatten[Transpose[#] & /@ all4x4, 1]

This yields the expected 9 arrays.