This is most likely caused by entropy coding, which is the final lossless stage of JPEG compression, after the image data has been quantized to reduce its size.

When a JPEG image is losslessly rotated, this final lossless encoding layer must be undone, the unpacked DCT coefficients shuffled around, and then the shuffled coefficients need to be entropy coded again. Since the efficiency of the entropy coding layer depends on the order of the DCT coefficients within each block, which rotating the image will change, it should not be surprising that the rotated image file may be a few percent smaller or larger than the original.

There are also several different ways in which the entropy coding step can be done, so it's quite possible that the file size of the exact same JPEG image may vary depending on the software that does the encoding. Some of the potential differences between encoders include:

• choice of arithmetic encoding (rare but potentially more efficient, used to be patented) vs. Huffman encoding (simpler, standard);
• choice of sequential (each 8x8 pixel block is encoded one at a time) vs. progressive (low frequency components of all blocks are encoded before the higher frequency components, usually slightly more compact) encoding order;
• choice of using the standard Huffman symbol tables (faster, simpler, may be more efficient for very small images) vs. custom tables optimized for each image (usually more efficient for large images, slower and more complex to encode);
• if custom Huffman tables are used, different encoders may potentially generate different tables for the same image data;
• various low-level details of the encoding process itself, such as whether and when to include restart markers in the data stream, may also vary between encoders.

Also, the "JPEG files" people normally work with actually contain JPEG-compressed image data wrapped in a JFIF or an Exif container, which combines the image data with one or more metadata blocks, and introduces its own set of complications. Even if the software that rotates the image does not actually make any substantive changes to the JFIF/Exif metadata, simply rearranging the data could potentially affect the file size by a few bytes.

In particular, the JFIF/Exif metadata may contain one or more thumbnails of the full-size image, and software that rotates images really should regenerate (or also losslessly rotate!) the thumbnails so that they will match the new orientation of the full-size image. This alone could easily account for the observed size difference.