I've been trying out Safari Restore and Sessions for a few days and I find they both remember the tabs from the previous session, but only the last page I looked at in each tab. There is no history for the tabs, ie, I can't click the Back button. "Reopen all windows" in the History menu does the same thing. Firefox and Chrome remember the entire session, so it's as if I never shut down. How do I get Safari to remember the actual session and not just the last page I looked at? Safari 5.0.4, 10.5.8
Obviously this wasn't a solution at the time you asked the question, but if you're looking for more basic, it's now built into the latest version of the operating system.
Safari in Lion does seem to remember the history for each tab when it restores on re-launch. If you were using 10.5.8 because you use PPC hardware, or don't want to buy the upgrade, this doesn't help, but it if Lion is a viable choice, it does seem to work very smoothly.