Construct compresses all images as .png, it doesn't matter what format you're importing.
But if you're importing a .jpg, then yes it will likely be a larger filesize than if you're importing a .bmp because jpeg compression is crap and causes extra color information due to artifacts. Png compression is optimized for areas of similar color, if you have lots of little changes in color information then the file size is going to go up.
This image is only 9.6kb, even though the physical dimensions are large. There is no change in color info from one pixel to the next.http://dl.dropbox.com/u/529356/smallSpray.PNG
This image is 33.6kb even though it's got much smaller dimensions than the first image. The reason is that there is a lot of change in color info from pixel to pixel. That's almost four times more disk space.
When you use .jpg compression, it causes little blurry artifacts at the edges of where colors change, in essence making a whole lot more colors than were there before. In short, .jpg is terrible for games and you shouldn't use it. Not only is it inefficient, it's ugly.
As for removing the sprite from the game and the .exe not changing size... did you remove all instances of the sprite, or just one copy of it?