Following the tutorial that you used, the message is displayed when the event triggers controller_action_predispatch_checkout_cart_index
thats why its showing only in checkout/cart
page, to display it in the other pages, it will be necessary to add the other events appropriate to these pages in your config.xml
in events
tag as you did for checkout/cart
<events>
<controller_action_predispatch>
<observers>
<stackexchange_freeshipping>
<class>stackexchange_freeshipping/observer</class>
<method>checkFreeShipping</method>
</stackexchange_freeshipping>
</observers>
</controller_action_predispatch>
</events>