Custom Shipping Method Availability in Commerce - User Messages
100% untested, but I think one way to go would be to use addError on one of the Commerce_OrderModel's attributes (in the defineAttributes method).

Then your template could do something like:

{% if 'myShippingMethod' not in craft.commerce.availableShippingMethods|keys %}
    {% for error in order.getErrors('theAttribute') %}
        {{ error }}&lt;br /&gt;
    {% endfor %}
{% endif %}