First let me sweep Quaternions under the rug. They are magic. They are wonderful. They are inscrutable.
So let’s forget about them.
The beauty of the transformation matrix is that you can look at it and see what is going on. I will show you how… but first I will digress a little. I’m going to try to explain why so that maybe it’s easier to remember and confirm.
Sorry if any of this is review.
Vector Projection
A unit vector represents direction. We say that because it is easy to plot things in that “direction”.
If we are at some location and we want to travel one unit in that direction then we just add it.
me + v = me there
If we want to travel 5 units in that direction then we add it 5 times. Or add v * 5.
me + v * 5 = me there farther
So let’s say we had two vectors representing an orthogonal set of axes. A rotation in space. One points down a new x-axis and the other points down a new y-axis.
If we want to figure out what x=4, y=5 in this new space is in our regular space we could travel xv 4 times and then yv 5 times.
me + x * xv + y * yv = me at 4,5 in rotated into regular space
This works in 3D also but you’ll have to trust me because I can’t draw in 3D.
But in 3D you would need three of these direction vectors. One to represent the x axis, one for the y axis, and one for the z axis. With these, given and x,y,z location we could figure out what x,y,z in this new space means in our regular space. Just like the 2D version above.
Put that aside for a second while I talk about matrix multiplication.
Matrix Multiplication
You will often see this explained a different way. For example, this site: http://www.facstaff.bucknell.edu/mastascu/elessonsHTML/Circuit/MatVecMultiply.htm
…has a nice animation showing it backwards for my purposes. So I will explain it myself… 
Given some matrix:
And some Vector: Vx, Vy, Vz
Step 1: Multiply the vector components by the columns.
Step 2: Add the column vectors together.
Rx,Ry,Rz is the result.
If the matrix was a rotation matrix then we get a rotated point as the result. But why?
If you’ve been following along then maybe it’s starting to become clearer why I did the multiply then the add.
The Rotation Matrix
In a rotation matrix, the 3x3 matrix is actually 3 vectors. The vectors represent the axes of rotation.
So in this matrix, we have three vectors…
Each of them is length 1 and they are 90 degrees from each other, ie: orthogonal. You can picture this in your head.
The Z axis is pointing straight up. The X and Y axes are rotated slightly because X in the X-axis vector is almost 1 and Y in the Y-axis vector is almost one.
Kind of like this: (I’m just drawing the x,y)
You can remember this by understanding how the matrix is actually doing it’s job. We can put together the things I talked about above. Matrix multiplication and vector projections.
If we want to project a x,y,z coordinate into this space then we’d project X down X-axis, add the projection of Y down the y-axis, and so on.
And well… isn’t that exactly what the matrix multiplication is doing? It multiples the x,y,z by each column and then adds those columns (ie: vectors) together.
Tada… now you should be able to visualize what a rotation matrix is doing. You might even be able to draw it on paper if you can’t graph in your head.
Transformation Matrix
The full up transformation matrix is an interesting beast in its simplicity. It almost feels like magic.
But wait… won’t the translation thing screw up our nice picture? No, in fact, here is the other reason I broke it down as multiplication then vector addition.
When you multiply a 3 component vector by a 4x4 matrix, you actually have to add a fourth component: 1
x, y, z, 1
So you’ll end up with four vectors and then add them together. From this it should be clear what order things happen in. (rotation then translation)
It is interesting to note that the bottom row of a column-major 4x4 matrix is basically useless in a regular transformation matrix. Many graphics-oriented math packages will just leave it out. (It is useful for a projection matrix but let’s pretend those are magic for now.)
So, what about scale?
Well, what do you think happens if you were to make those axis vectors non-unit? What if x-axis, y-axis, and z-axis were actually length 0.5 instead of length 1?
I’ll leave that as an exercise for the reader since I’ve already hand-drawn on imgur images too many times in this post.