Disabling this is not really a supported feature in Safari, so it would be interesting to know the motivation behind your need to disable it? Is it only to know where someone has been?
----
HACK! BACKUP SAFARI BEFORE PROCEEDING!
Disable Private Browsing using Interface Builder (see step 4 on how to get it)
1. Locate Safari in /Applications and Archive it (Right click/Control+click Safari and choose Make Archive).
2. Right click/Control+click Safari and choose "Show Package Contents"
3. Go to Contents, Resources, English.lproj folder or the folder for the language you want to edit, or multiple if you have multiple languages involved.
4. Doubleclick MainMenu.nib to open in interface builder (this requires that you installed XCode, which is often on the install DVD for MacOS X if you haven't installed it, or you can register for a free Apple Dev membership on
http://developer.apple.com/ and download it for free there. You only need the latest version usually. Then repeat this step when you have it installed.
5. Look at the window with the safari menu, click on Safari to expand it, then click on the Private Browsing menu item.
6. Press the Delete key to disable it.
7. Cmd+S to save, then quit Interface Builder and launch Safari.
-------------
The better and more ideal way to "solve" this issue, since a user could download another browser and run from their home folder to get around it, is to configure some kind of proxy and then direct all network traffic through that.
You could install MacOS X Server and configure a workgroup that the other Macs were member of and then use Workgroup Manager in that to configure their desktops, including Safari.