Using OS X 10.7.2 and Safari 5.1.2
I was looking for a solution to get Safari to open an url and go full screen without any toolbars or anything. Getting the first part is no problem. The issue is that the menu item "Hide toolbar" is in active when Safari is in fullscreen.
As described in earlier replies one can do this by control click on the toolbar and choose hide toolbar but I needed it to be automatically. Accessibility Inspector (which is a small app included in XCode) to the rescue. With this I could start exploring the UI elements of the Safari window. I got everything up and running in plain mode but nothing in fullscreen mode. This was because Safari re arranged the UI elements when it moves to full screen mode. (Some hours of head scratching...)
The toolbar menu in window mode is
window 1 > tool bar 1 > menu 1
in fullscreen
window 1 > group 2 > tool bar 1 > menu 1
So here is my applescript for "Open url in fullscreen mode in Safari"
tell application "Safari"
# Start or focus Safari
activate
# Start or focus Safari
open location "http://apple.com"
tell application "System Events"
tell application process "Safari"
# Fullscreen
tell window 1
click (every button whose description contains "full screen")
end tell
# Wait for safari
delay 2
# Trigger toolbar menu "Hide toolbar"
perform action "AXShowMenu" of tool bar 1 of group 2 of window 1
key code 125
keystroke return
end tell
end tell
end tell