If they're JPEGs, yes it could be normal.
JPEG compression works by identifying bits of the picture which can be described more economically than having to describe each pixel separately. Large areas of colour, regularly varying colour, that sort of thing. Noise is essentially random though, and there's no relationship between the pixels in a noisy photo so the JPEG compression doesn't work very well and you get a large file. When you run noise removal software, it sort of averages out the noise and creates regularity and patterns and relationships between the pixels which the compression algorithms can exploit - so you get a smaller file.
Make sense?