For the record, we’re talking about this:

The problem is that OS X doesn’t remember if you uncheck the checkbox on the last shutdown — it will always keep the checkbox checked by default on subsequent shutdowns.
I found two different solutions for this problem, that seem to do the trick, although they aren’t ideal.
Open Terminal.app and enter the following commands:
defaults write com.apple.loginwindow TALLogoutSavesState -bool false
defaults write com.apple.loginwindow LoginwindowLaunchesRelaunchApps -bool false
This effectively disables the “reopen windows when logging back in” option, although the checkbox will still appear to be checked. You can just ignore it.
I’m afraid there’s no better solution, at least not at the moment.
Update: OS X 10.7.4 fixed this — it now remembers your selection:
