I have a class that holds a 4x4 matrix for scaling and translations. How would I implement rotation methods to this class? And should I implement the rotation as a separate matrix?
You can multiply Your current matrix with a rotation matrix. Take a look at http://en.wikipedia.org/wiki/Rotation_matrix
There's a site which I use every time when I need to look up the details of a 3D transformation, called http://www.euclideanspace.com. The particular page on matrix rotations can be found here.
Edit: Rotation around a given axis, look at the axis & angle representation. This page also links to a description on how to translate one representation to another.
If you need to rotate around mutiple axes, simply multiply the corresponding matrices.
Answering the second half of the question, a single 4x4 matrix is perfectly capable of holding a scaling, a translation, and a rotation. So unless you've put special limitations on what sort of 4x4 matrices you can handle, a single 4x4 is a fine for what you want.
As for rotation about an arbitrary vector (as you are asking in comments), look at the "Rotation about an arbitrary vector" section in the Wikipedia article yabcok links to. You will want to extend that to a 4x4 matrix by padding it out with zeros except for the 4,4 (scaling) position, which should be one. Then use matrix multiplication with your scaling/translation 4x4 to generate a new 4x4 matrix.
You want to make sure you find a reference which talks about the right kind of matrix that's used for computer graphics (namely 3D homogeneous coordinates using a 4x4 transformation matrix for rotation/translation/skewing).
See a computer graphics "bible" such as Foley and Van Dam (pg. 213), or one of these:
This page has quite a bit of useful information:
http://knol.google.com/k/matrices-for-3d-applications-translation-rotation