This is exactly what customizable sidebar sections and links are intended for.
from the description of the welcome link banner that Nate suggested:
from the settings interface of the actual versatile banner component Nate also linked:
Having used both components, I can tell you they can be made to appear on every page exactly the way you want and are very customizable. Please at least check out suggestions and try them before dismissing them as not a possible solution.
@NateDhaliwal has the correct idea - if these components do not do what you want, it is relatively straightforward to build a simple theme component that does.