I'm turning a comment I made into an answer to further explain why I think that smaller size doesn't necessarily mean a loss of quality, although it often does.
I believe generally that MSPaint will degrade the quality of your images when you save them for the exact reasons Guffa illustrated. However, it doesn't always change the quality even though it might change the filesize. One file I tried just now actually grew by 10% in size and the quality was exacty the same.
You can test for quality difference by opening both images in Photoshop and blending them with 'Difference'. The differences are usually pretty subtle, but you will see a few odd pixels close to black but not quite that indicate a difference.
Now, MSPaint has no way to set the jpeg quality you save an image so we can only assume it is saving with a quality of maybe 75% (who knows?).
Other programs can give you finer control of quality settings, but I just now created three files of the same image and all three are different sizes even though there is no difference per pixel between those files. They are of an image 940x350 pixels and they have file sizes of 194,571; 188,924; and 170,074.
The first was saved from Photoshop CS5 using Quality:10 and Baseline "Standard" settings, the second was saved using Quality:10 and Baseline Optimized settings and the third was saved from the 'Save for Web & Devices' option that offers quite a bit more control over the quality settings of the file. Here I used 80% Quality and checked the 'optimized' box. All of these images are identical pixel for pixel.
My point is that just because a jpeg file is smaller, it doesn't mean that there has been some quality loss.
Why not? What is going on?
If you take a jpeg file with large areas of similar color and saved it 'optimized' it could actually lose a significant amount of size because there is another algorithm called huffman coding that is applied after the jpeg blocking.
So to answer your question: the only way to know for sure about quality loss is to do a pixel-to-pixel comparison with a 'Difference' layer. Its a good bet that with MSPaint you are, in fact, losing quality.
Here is a link to more info on Huffman Coding
Some applications have a fixed Huffman table that they use for all images. While others will try to build an 'optimized' huffman table specific to the data in that file.