The basic algorithm is to use a Hough transform to find the lines and then try to make most of the lines horizontal. Here's some basic code http://www.sydlogan.com/deskew.html
For your situation, you might want to target the transform at a piece of the image you know might have the best information. For example if there's a page border -- I'd need to see an example to give better advice.
Disclaimer, I work at Atalasoft.
Our DotImage toolkit has it built in for .NET and is runtime royalty-free for desktop applications. Code would be:
AtalaImage img = new AtalaImage("imagefile.tif");
AutoDeskewCommand cmd = new AutoDeskewCommand();
AtalaImage resultImage = cmd.Apply(img).Image;
resultImage.Save("result.tif", new TiffEncoder(), null);
Or something similar for multipage or other types of images.
We show how to integrate it with our viewer control in this video (at 1:14)
http://www.atalasoft.com/products/dotimage/tutorials/capture/lesson4.aspx
The videos are part of a series of building a document scanning application:
http://www.atalasoft.com/products/dotimage/tutorials/capture/lesson1.aspx
http://www.atalasoft.com/products/dotimage/tutorials/capture/lesson2.aspx
http://www.atalasoft.com/products/dotimage/tutorials/capture/lesson3.aspx