Found a very interesting tool to do lossless rotation and EXIF editing of JPEG files. Checkout jpegtran. This version is apparently a patched version of the JPEG software from IJG.
jpegtran -copy all -rotate 90 1.jpg
There is also a related tool, jhead, which can pull all sorts of interesting stuff out of JPEGs. This will extract a thumbnail which most cameras already embedded in photos:
jhead -st "thumbnails &i" *.jpg
And finally, another tool and script which can auto-magically rotate files based on the orientation info in the header.