It will depend on what desktop environment you use...
I use KDE, and HAD a PowerOff icon on my desktop. I have KDE to respond to a single-click, and used to occassionally click the PowerOff by accident. I've since deleted it.
I created it by right-click on the desktop, and choosing Create New / Link to Application. In the General tab, I named it PowerOff, and chose a spiffy icon. In the Execute tab, the command was simply "poweroff". This, of course, depends on users being able to use the command. Replace poweroff with reboot, and it should work for you.
For GNOME, or others, I don't know, but the process would prob'ly be similar.