Using explicit handles to the patch objects will fix the legend for you. Also, you don't need the second call to hold on. The last part of the code will delete all line objects in the plot. If you want to change the legend labels, look into the doc for the legend function.
S=load('matlab.mat');D=S.D;I=S.I;NO=S.NO;
figure(1),clf(1)
yt = logspace(-3,4,8);
binranges = yt;
[bincounts] = histc((I(:,1)),binranges);
h1 = bar(binranges,bincounts,'histc');
set(h1,'FaceColor','r','EdgeColor','r');
hold on;
[bincounts] = histc(1./(D(:,1)),binranges);
h2 = bar(binranges,bincounts,'histc');
set(h2,'FaceColor','g','EdgeColor','g');
%hold on;%redundant, as the NextPlot property is already set
[bincounts] = histc((NO(:,1)),binranges);
h3 = bar(binranges,bincounts,'histc');
set(h3,'FaceColor','b','EdgeColor','b');
legend([h1 h2 h3]);%use handles to patch objects
set(gca,'XMinorTick','on','YMinorTick','on','XScale','log');
children=get(gca,'Children');
types=get(children,'Type');
delete(children(ismember(types,{'line'})))
