Rough answer : almost all small dims can appear, there are some restrictions to
large dims.

For example, considering 1 matrix all dims between 1 and n appear.
Taking centralizers of these all numbers of the form sum a_i^2 where a is a partition
of n appear.

In general, consider k-tuples of positive integers a and b such that their scalar product
a.b=n (a should be thought of as the Morita setting, b as the matrix-sizes of the semi-simple part 
of the subalgebra), then any number of the form

sum b_i^2 + subsum b_ib_j

is possible (here 'subsum' means that one takes all terms b_xb_y for all x,y in a 
substring 

1 <= i_1 < i_2 < ... < i_l <=k for any 0<=l<=k)

Edit : the subsum gives the dimension of the Jacobson radical. This answer cannot be the final one, as it only detects the subalgebras of global dimension 1. For example any n-diml algebra can be embedded in nxn matrices.

There are some obvious restriction wrt large dimensions. For example, there cannot be an 8-dml
subalgebra of 3x3 matrices as its semi-simple part can be at most C x M_2(C) and so its dimension must be
smaller or equal to 7. 

For general n there cannot be subalgebras with dimensions between the dim of the largest parabolic
subgroup of GL(n) and n^2.

Edit : a closely related question can be found here : <a href="http://mathoverflow.net/questions/19755/problems-concerning-subspace-of-m-nc">problems concerning subspaces of mxm matrices</a>.