Let me first describe a simple partial solution for people who just want something to understand quickly:
"For each of the 2 rectangles, check whether any of its vertices is within the the other rectangle."

That's a short explanation, isn't it? It's just too bad that it doesn't work sometimes. Can you see when?
When can two rectangles partly overlap without any of them having any of its vertices within the other rectangle? If you haven't got it, think of a cross, or just click here.
In most simulations, such situations aren't supposed to occur since the collision response mechanism detaches the rectangular objects before they can form a cross. However, who said this routine is to be used for physical simulation only? Another note to justify the explanation to come of the more complicated solution is that it's efficient (note that you can optimize the vertex check solution by combinining the tests of the vertices in the same rectangle, but it still doesn't get as fast as the following solution).

Each rectangle will be represented by [center{x,y}, size{w,h}, alpha]. First, let's translate the plane by (-rect1.center.x, -rect1.center.y) to make rect1.center unify with the origin. Second, we'll rotate the plane by -rect2.alpha to make the second rectangle axis aligned. Note that it works even though rect2.center doesn't necessarily unify with the origin.

Note: I'd suggest you download the C sourcecode attached and follow it as you read the tutorial if you have problems understanding any part of this tutorial.

We now have the first rectangle (rect1) centered around the origin and the second rectangle (rect2) axis-aligned (we have somehow spread the complex properties rectangles may have, uniformly between the two rectangles). We'll now note the obvious features of rect2 (or any axis aligned rectangle), namely that: (1) It's wholly contained between its left side, x=Left, and its right side, x=Right (We'll call that region the Horizontal Range, H-Range in the applet), and (2) in this limited region, it covers the whole area between its upper side, Y=Top, and its bottom, Y=Bottom (This is NOT the V-Range in the applet, it is the region Rectangle 2 cuts from the H-Range). Due to (1), it's obvious that we can check for collision between rect2 and the part of the rect1 which is bounded by the infinite lines x=Left and x=Right, we'll call this part, Shape1 (if this region does not contain any part of the rect1, collision is impossible. I'd suggest you play with the applet to understand what Shape1 is). (2) makes it clear that it is enough to check whether Shape1 has any point bounded between the upper side of the second rectangle and its bottom.

But a rectangle is a convex polygon and therefore Shape1 will be cut "in one piece". That means, for our purposes, that if (X1, MaxY) is the highest point of Shape1, and (X2, MinY) is the lowest point of Shape1, then for any Y between MinY and MaxY, there's an X such that (X, Y) is a point within Shape1. Therefore, checking if Shape1 has any point bounded between the upper side of the second rectangle and its bottom, is equivalent to checking whether there's any Y value between MinY and MaxY, which is also between Top and Bottom. This is equivalent to checking whether two segments in a 1D enviroment intersect. We've actually found a general algorithm of testing for intersection between a rectangle and any convex polygon, but in the rest of this article we'll assume that this other convex polygon is a rectangle too. This leaves us to find a way to quickly find MinY and MaxY (The region between MinY and MaxY is called the Vertical Range, the V-Range in the applet):

Since rect1 is centered around the origin, it is symmetric around the X Axis and around the Y Axis. It has two pairs of opposing vertices, one which is the highest and lowest points of the rectangle and one which is the leftest and rightest points. Due to the symmetry just mentioned, we'll denote these pairs of vertices (A, -A) - Vertical Min/Max, and (B, -B) - Horizontal Min/Max.

The orientation of rect2 determines which pair of vertices is (A, -A), and which is (B, -B). This property flips every 90 degrees of rotation and therefore it can be figured out by the sign of sin(rect2.alpha)*cos(rect2.alpha) (this is done after rotation of the plane by -rect1.alpha, so the actual angle here is rect2.alpha-rect1.alpha = ang, see the C source code attached).

First, we'll check whether Shape1 exists, by comparing the ranges [B, -B] and [Left, Right].

We don't have to check which of A and -A is the vertical maximum and which is the minimum because we treat them in the same manner. We'll find Shape1's highest and lowest Y values, MaxY and MinY, and store them in the variables ext1 and ext2 (without knowing which is the maximum and which is the minimum).

We'll check whether A is in the Horizontal Range (between x=Left and x=Right). If it is, it is obviously Shape1's extremity. If it's on the right of this region, the extrimity would be the interestion point of the segment AB and the line x=Left. If it's on the left, the extrimity would be the intersection point of the segment A(-B) and the line x=Right.

To code this well, first compute the differences Right-A.x, Left-A.x. If they have different signs, A.x is between them and A.y is our extremity. If they have the same sign, check which sign it is. If it's negative (case 1), A.x is on the right, and if the sign is positive (case 2), A.x in on the left. Now calculate the slope, case 1: (A.y-B.y)/(A.x-B.x) or case 2: (A.y-(-B.y))/(A.x-(-B.x)), multiply it by the precalculated horizontal distnace from A: case 1: Right-A.x or case 2: Left-A.x and add this to A.y to get the extremity.

	dx1 = Left-A.x; dx2 = Right-A.x; // Calculate difference
	ext1 = A.y;
	// If A.x is within x=Left and x=Right, this is the exterimity,
	// otherwise, it will be used to calculate dy (= A.y-B.y or A.y-(-B.y) = ext-B.y or ext+B.y).

	if (dx1*dx2 > 0)
	{
	 dx = A.x;
         // dx = (A.x-B.x),    dy = (A.y-B.y),    dx1 = (Right-A.x)
	 if (dx1 < 0) { dx -= B.x; ext1 -= B.y; dx1 = dx2; }
         // dx = (A.x-(-B.x)), dy = (A.y-(-B.y))  dx1 = (Left-A.x)
	 else         { dx += B.x; ext1 += B.y; }
         // ext1 = A.y + (dy/dx)*dx1
	 ext1 *= dx1; ext1 /= dx; ext1 += A.y;
	}

Do the same with -A instead of A to find the other extrimity, ext2.
Now conduct 1D segment intersection test between [ext1, ext2] and [top, bottom].