TLDR; assuming my calculations below are correct, there's roughly a 10% increase in air resistance between hot, humid days, and cool, dry days. Add in a slight but imperceptible tailwind or headwind, and it's conceivable that you could experience a 4–5mph difference in cruising speed between two days.
Air resistance is the primary force a cyclist must overcome at typical cruising speeds. According to one online calculator, assuming a typical road bike, a relaxed riding position, and a cruising speed of 18mph, 75% of a rider's power is used to overcome drag.
According to your profile, you live in Melbourne, AU, which is essentially at sea level. Using another online calculator, the air density when it's 50˚ and 0% humidity is 1.24kg/m³. When it's 90˚ and 100% humidity, the air density is 1.13kg/m³. So, on a cold and dry day, there's roughly a 10% increase in air resistance when compared to a hot and humid day.
According to the drag equation,
the drag force scales linearly with air pressure. 10% higher density equals 10% higher force necessary to overcome drag. Instantaneous power is determined by the equation
Assuming constant power output, and 75% of that power is dedicated to overcoming air resistance, you end up with roughly a 7% reduction (1 / 1.075) in overall speed. We started with a cruising speed of 18mph, so simplistically your speed on a cold and dry day would wind up being 93% of 18mph, or 16.75mph. I'd say that's enough to notice.
Of course, it seems unlikely that these two days would occur closely together. But if you're comparing a midday ride just before or after a storm to a late evening ride on a dry day a few days before and/or after, it's conceivable that you could wind up somewhere in the ballpark of a 1mph difference.
That said, even a small headwind and tailwind can make a significant difference in your speed. Sheldon's site has graphs showing wind tunnel tests. In particular,
shows that as the wind angle changes from a headwind to a tailwind for a 5mph wind, a rider traveling at a "normalized" speed of 25mph (assuming no wind) would go from roughly 22mph to 28mph. The difference in rider velocity as wind velocity changes seems to be linear, so extrapolating backward, even something like a 2mph headwind vs. tailwind would cause something like a 3mph difference. That's definitely noticeable. Being in a wind tunnel, these tests weren't done with rolling resistance, so 25mph in the wind tunnel is probably equivalent to our earlier assumption of 18mph on outdoor roads.
If you combine the effects, and compare a late evening ride on a dry day with a slight headwind, to a early afternoon ride on a humid day with a slight tailwind, you could conceivably have a difference of 4-5mph between the two days. That's huge.