Booking the "day of" route has it benefits and it's drawbacks. Weather or personal mood may be considerations for some people, and that is fine, but if you are going to do the "day of" bookings you better be ready to have a "day off" also on occasion. At least in Kona, some companies really are full, almost every day. Some almost always have a spot or two avaialble. Some of the operators who go out a lot, but not everyday if not booked, or have a spare boat available, won't go out on a couple hours of notice or less unless they have enough customers and also crew standing around by the phone waiting... and that's very rare here.
One note, during the upcoming holiday season, and also during the spring/easter break period and oftentimes during the summer, last minute charters can be tough or impossible to come by here. A lot of it depend on where, and when, you travel.
Cancellation policies do seem to run the gamut, so it's always worthwhile to investigate. Also, at least in Kona, just because the water and wind and clouds are snotty at your hotel doesn't mean it's not flat, sunny and calm out on the water where the dive boats are going... that's a huge rub here in Kona as the weather and wind conditions north of the airport are often completley unrelated to the conditions south of it, and the major resorts are to the north. Most operators are out to show their customers the best diving they can and will cancel if conditions merit.
I feel like I'm ranting, but I get my share of calls around 8-8:30 in the morning from people looking for a ride that aren't likely to find one no matter how many numbers I give them when I can't help.