Gallery doesn’t yet automatically rotate images using the EXIF orientation data that newer cameras save in the file, though it will soon. In the meantime, jhead can automatically rotate the images, like so:
jhead -autorot *.jpg
And I think that’s lossless. You can run it on already-uploaded Gallery images from the terminal.
By the way, it looks like GNOME’s Image Viewer will finally support automatic rotation soon.