Concerning graphic outputs, I use the following trick each time I have a big plot

...A plot... // Rasterize

for instance:

ArrayPlot[M] // Rasterize

Using rasterized outputs significantly reduces the notebooks size.

Take a look at:

http://mathematica.stackexchange.com/questions/87102/notebook-cells-space-on-disk-profiler/87117#87117

I use the palette developed by Albert Retey to identify lager cells in my notebooks. Also, you can open the notebook in a good text editor to have a better idea of what is going on.

Notebook history would have nothing to do this this--calculation history is contained in Mathematica memory for the current session, not in the notebook.

If you have 3D graphics then one can get very large notebooks.

If you remove all output and all graphics (do this on a copy of the notebook, of course, so you don't loose your current results) does the size of the file drop down to a reasonable one.

If so, and is should, one can then experiment by deleting just specific parts of the notebook -- particular graphics -- to track down the culprit.