I notice many sites have really smart tabs on for selecting pages, is there a program that does this or site, or do people do them from scratch on Paint Shop?

Both...

There are many application specialized just for making tabs, buttons and menus.
But if You wanna be original, use Photoshop or Fireworks or ...whatever app for image editing.

It is really easy in a graphic editor program like photoshop. If you want some tutorials check Good-Tutorials.com · 11,129 Adobe Photoshop Tutorials

You could also use this: CSS Tab Designer