If you kill nautilus (or it's otherwise not running) your icons won't show on the desktop. Another reason they won't show is if in gconf the key name show_desktop is set to false. To check whether the latter is the case, open gconf-editor (hit ALT+F2 and run it there) and look under apps/nautilus/preferences.
Bookmarks