It's not that hard to see how a rotation can end up being represented by a matrix of dimension $(2j+1)\times(2j+1)$. The key concept is that this matrix acts on a subspace $V$ of the Hilbert space $\mathcal H$; that is, $V$ contains state vectors (kets). Generally, $V$ is required to be an invariant subspace in the sense that if $v\in V$, then under a rotation $v$ will in general go to some different vector $v'$ but it will nevertheless stay in $V$.
The easiest way to see this is by way of example, so let me show how this works for $j=2$. There are in general many possible realizations of $V$, but the cleanest realization is as the vector space of functions $f:\mathbb R^3\to \mathbb C$ which are homogeneous polynomials of degree 2, and which are 'traceless' in the sense that
$$
⟨f⟩=\int_{S^2} f(\hat{\mathbf{r}})\,\mathrm d \Omega=0.\tag1
$$
This vector space is best analysed in a convenient basis, and the cleanest one is
$$
B=\{x^2+y^2-2z^2, xz, yz, xy, x^2-y^2\}.
$$
It is fairly easy to see that $V$ is closed under rotations, because each vector component will go into a linear combination of $x,y$ and $z$, and multiplying any two such combinations will again give a homogeneous polynomial. Rotations will also not affect the tracelessness condition (1).
To calculate the effect of a rotation $R\in\mathrm{SO}(3)$, you simply take a given $f\in V$ to the function $G(R)f\in V$ which is given by
$$(G(R)f)(\mathbf r)=f(R^{-1}\mathbf r).$$
(The reason for the inverse is so that the operators $G(R)$ have the nice property that $G(R_1\circ R_2)=G(R_1)\circ G(R_2)$, so that $G$ itself is a homomorphism between $\mathrm{SO}(3)$ and the group of unitary transformations on $V$, $\mathrm{U}(V)$.)
For any given $R$, $G(R)$ is a geometrical transformation but it is also, at a simpler level, a linear transformation in a finite-dimensional vector space $V$ with basis $B$, so you can simply represent it by its matrix with respect to this basis. Thus, for example, a rotation by 90° about the $+x$ axis would be represented by the matrix
$$
\begin{pmatrix}
-\tfrac12&0&0&0&\tfrac12\\
0&0&0&-1&0\\
0&0&-1&0&0\\
0&1&0&0&0\\
\tfrac32&0&0&0&\tfrac12\\
\end{pmatrix}.
$$
(Work it out!)
The others have given more detail on how this works mathematically - the function $G$ being a representation of the group $\mathrm{SO}(3)$ - but I think that examples of this sort help a lot in visualizing what's going on.