Close
Just free transform to line up. Put each part in a separate layer, and find a spot near the top of the image that lines up; if there's no overlap, it's easiest with two straight lines that cross the boundary in different directions, so you can line it up on both axes, but sometimes it takes some guessing.

Then free transform on one of the layers, drag the anchor point (the dot that appears in the center of the layer) to the point near the edge that's most correct, scroll down to the bottom edge which is off due to the rotation, and change the rotation (don't drag the transform outline; select the rotation input at the top and press up/down to change .1 degree at a time) to line it up. Since the anchor is at the spot that's lined up, it won't break that side of the image.

If both parts are unwarped, this usually can get it very close. If you only have one line crossing across, it can be trickier: you can line up the line, but not know how big the gap should be, and it can take some experimentation. Sometimes you only have rounded eges to work with, which is trickier.

One major limitation in Photoshop is that you can only rotate in free transform by 0.1 degree; sometimes this is too coarse, so 0.3 will be rotated too little and 0.4 too much; 0.35 will just round to 0.4. This is really annoying. If you use Image/Rotate Canvas/Arbitrary, you can rotate by much finer increments, but that will only rotate the entire image and not one layer, so you have to split the layers apart, and you lose the benefit of being able to see the preview in realtime.

If your image has strict horizontal or vertical lines, it's a big help. Keep each part in a separate image, select the ruler tool, drag it along the sharp edge. Zoom in and line it up exactly, then hit rotate/arbitrary and it'll fill in the rotation needed to make the ruler horizontal or vertical. Repeat for the other part. If both images have an edge like this, then it'll rotate both exactly, so you only have to line them up. (post #57830) Beware of doing this with the edge of the paper rather than a feature in the actual printing (the print itself may be slightly off), but it's also worth trying if you're having trouble.