I'm having the same problem.
Only way I can get it to stay full screen is if I check off "reopen windows when I login" when I log off my system, and that is if I leave Safari open when I log off.
Otherwise, anytime I launch it, it doesn't open in full screen, just in a window.
I recently re-installed Lion, this never happened before.