The challenge is branding and selecting a method to do so, not whether it is SPS or WSS. Both SPS and WSS run off site definitions. You can manually go into the site definition files (a collection of ASPX and XML files on the web server) and make layout changes. A major drawback to the SharePoint layout code, is that it is not centralized. So the same layout code is in every file and thus every file has to be updated. Depending on how many list definitions the site definition includes, the number of files that has to be edited can grow quite large.
In addition to site definition file edits, you can alter the way a WSS sites looks with a theme (which is a collection of CSS and image files).
You can make more limited branding changes to either SPS or WSS through editing CSS and images.
With that brief “what is what” explanation out of the way, here are your options IMHO:
1) Try to add a banner using a theme – you tried this already and it would only appear on the home page.
2) Get tricky with CSS and/or JavaScript and try to insert the banner on each page above the existing nav bar. I have not done this personally, so it is just a suggestion.
3) Create a custom site definition based off the STS site definition and add the banner to each ASPX file where needed. This will be time and labor intensive.
May I suggest an alternative way to look at this banner as well… Through CSS tweaks, you can shift the WSS top site navigation over to the far right, opening up the left side for a custom logo or graphics. This does not create a “banner above” but may give you the space you are looking for. If you use this method, you only need to work with the CSS and some images. No intensive site definition labor will be required. You can also open up the size of the existing navigation bar to be taller and provide more space for a logo or custom graphics.