On the checkout page the following message is displayed when a location that doesn't have any applicable shipping methods is selected:
Please enter your post code above to see available shipping options. No Shipping methods are available for the selected location.
It would be great if merchants could customise this message in a similar way to how the free shipping label can be edited.