While I have never implemented any rotation algorithm, I think it would help to actually do it on paper first...
Draw a rectangle on a squared paper, where each square represents a pixel. Label each square with the coordinates of the pixels. Then turn the paper 90 degrees, and draw a second equally large rectangle, again with each "pixel" labeled with the coordinates.
Now when you turn the paper back so the first rectangle is normal, you can easily see where to put the pixels in the output (second) rectangle.
It shouldn't be too hard to find a general algorithm for that.