Adding to the trouble is that Mail.app and the Finder will also "auto-correct" the rotation, so it can be hard to tell which images need to be "fixed" and which don't.
You could use the '/usr/bin/sips' program (sips --rotate 90 picture.jpg) if you knew which pictures need to be corrected, and which direction they need to be rotated (clockwise or counter-clockwise). But I wanted something that would, as they say, "just work."
(I also wanted something I could use on my webserver, which runs Linux, but that's really a side issue.)
My attempts to find a solution on Google were fruitless, so I asked on Twitter. Michael Baltaks pointed me to jhead, which describes itself as a "Exif Jpeg header manipulation tool" which includes the source code as well as pre-built binaries for OS X, Linux, FreeBSD, and even Windows.
To fix a picture named "image.jpg" just type "jhead -autorot image.jpg" and you will see "Modified: image.jpg". You can fix all JPGs in the current folder using "jhead -autorot *.jpg" and it will only change the images which have the EXIF tag.
Note: You might be tempted to use the "-norot" argument, which will "zero out" the rotation tag, but it will not have the desired effect, and (even worse) once you have used the "-norot" you can't use "-autorot" -- trust me, I learned that one the hard way.