The group SO(3) can be represented (and defined) by 3-by-3 matrices as most of us have seen many times before.
But in "Group Theory in a Nutshell for Physicists", we "construct" an 8-dimensional representation by stacking two one dimensional and two 3-dimensional representations "on top" of each other, and we get an 8-dimensional (obviously reducible) representation. But I cannot comprehend how an 8-dimensional representation would even make sense when talking about rotations in 3 dimensions. The original 3-dimensional representation would work on a 3-dimensional vector but how would an 8-dimensional matrix be able to perform any meaningful operation on such a vector? Am I missing the point?
Yes, you are :-). You're looking at a very specific and rather anomalous case where a group happens to be defined in terms of linear maps on a vector space – that's not the best way to get to grips with the concept of a linear representation, since it invites you to confuse the defining representation with representations in general.
Better to start with a different example. The symmetric group $S_n$ can act linearly on all sorts of vector spaces. For instance, on the space of real-valued functions on $n$ elements, yielding an $n$-dimensional representation (which decomposes into a $1$-dimensional and an $(n-1)$-dimensional irreducible representation). Or on the space of real-valued functions on ordered pairs of $n$ elements, yielding an $n^2$-dimensional representation (which contains a copy of the $n$-dimensional representation in the previous example).
So a representation and its possible dimensions have nothing to do with any dimensions that may occur in the definition of the group, as most groups (like $S_n$) have nothing to do with vector spaces.
In the case of $SO(3)$, consider how the group acts on $3\times3$ matrices, where the action of an element $O\in SO(3)$ on a matrix $A$ is defined by $O^\top AO$. This is a linear action on the $9$-dimensional space of $3\times3$ matrices, and thus a $9$-dimensional representation of $SO(3)$. Multiples of the identity transform among themselves and thus form a $1$-dimensional subrepresentation. Antisymmetric matrices also transform among themselves and thus form a $3$-dimensional subrepresentation. Traceless symmetric matrices also transform among themselves and thus form a $5$-dimensional subrepresentation.
This $9$-dimensional representation happens to have a clear physical interpretation in $3$-dimensional space. For instance, the moment of inertia of a body is a symmetric $3\times3$ matrix, which you can decompose into a scalar part and a traceless part. When you rotate the system, these transform according to the above $1$-dimensional and $5$-dimensional subrepresentations, respectively. But representations don't need to have such interpretations; all that's required for a representation is the abstract property that the multiplication among a set of linear maps on a vector space corresponds to the group multiplication.