Software like Google Picasa demonstrate very well that software can figure out which way a photo was taken without Exif-Data as it is not available in every camera.
Is there a documented algorithm which outputs whether or not an image has to be rotated or not? I want to find out the rotation without the use of EXIF Data. If at all possible I would want to do this with ImageMagick.
This is a complex problem and subject to ongoing research accordingly. Yann's answer is basically pointing towards the usual approaches already (+1) and mfrellum's hint towards the subject of Pattern Recognition likewise applies as well (+1) - for a more in depth analysis you might want to read through a couple of the following papers (subjective selection from past research of mine):
[Please note: most of the PDF links below have been deduced from Google Scholar - Google is naturally good at finding the matching PDF elsewhere for publicly available abstracts of papers, where the actual content is more often than not hidden behind paywalls. The legality of this is subject to heated discussions of course, and so is shielding regularly publicly financed scientific research like so in the first place - make your own judgement!]
One of Hongjiang Zhang many follow up papers is Content-Based Image Orientation Detection with Support Vector Machines (Yongmei Wang and Hongjiang Zhan - 2001)
Another (though less illustrative) one is Boosting Image Orientation Detection with Indoor vs. Outdoor Classification (Lei Zhang, Mingjing Li, Hongjiang Zhang - 2002)
Accordingly, a summary of the aforementioned approaches is Detecting image orientation based on low-level visual content (Yongmei Michelle Wang and Hongjiang Zhang - 2003)
A quite sophisticated one is A Probabilistic Approach to Image Orientation Detection via Confidence-Based Integration of Low-Level and Semantic Cues (Jiebo Luo and Matthew Boutel - 2004)
The best match regarding your question title is actually Image orientation detection with integrated human perception cues (or which way is up) (Lei Wang, Xu Liu, Lirong Xia, Guangyou Xu, Alfred Bruckstein - 2003) ;)
Finally, you might want to have a look at a respective patent regarding a system and method for automatic digital photo orientation detection (2008) - the basic algorithm is summarized with great detail in Figure 8 ;)
Unfortunately I'm not aware of any readily available implementations/libraries, though I'd be surprised if there wouldn't be a few bits available at least.
Have fun :)