What is the order group policy settings are applied?

Software installation policy is processed before Startup Scripts are executed. Sometimes that's exactly what you want, and other times it's not. You can't change it.

When I want a startup script to run before software installation I end up using group membership to control the execution of the startup script and I end the startup script with a command to add the computer to a second group that controls software installation. The only problem with this is that, to date, I have yet to find any reliable way to restart a Windows XP or newer OS from a startup script. (Yes, yes-- I've tried a variety of methods, too. I can discuss them in detail if you'd like.) As such, this always makes this strategy require two boots to "take effect".

You mention "preferences", so I think you're looking at doing things to the user's environment via a logon script. Logon scripts are executed, obviously, after logon. If you're looking to check to see if a piece of software has been installed during the logon script query the Windows Installer "database" in the registry to see if the program is there and "bail out". You'll find the installed products in the "HKEY_CLASSES_ROOT\Installer\Products" key. Obviously, you'll have to figure out the GUID for the package you're dealing with.

Edit: Group Policy client-side extension (CSE) processing order is performed based on the value of the GUID for the client-side extension, from what I've been able to glean from documentation. It looks like the CSE's with numerically higher GUIDs execute later. I don't have the GUID for the "Preferences" CSE handy so I can't tell you how it should act re: running before / after other CSE's.

On Windows XP, at least, dig into HKLM\Software\Microsoft\Windows NT\CurrentVersion\WinLogon\GPExtensions and look for the CSE for "Prefernces". REGEDIT will sort those GUIDs numerically, too, so you could be able to tell, visually, if that "Preferences" CSE is going to execute before/after other CSE's.

There are two kinds of scripts that are run. Startup scripts are run after computer preferences are set (things in the Computer Settings part of the GPO). Login scripts are run after the user logs in and the User Settings are applied. Scripts are run synchronously in the order that they are listed in the GPO (so one script has to finish before the next can start). Note that by default Windows XP will actually let you login before Network Settings have been processed, which means that you can logon before GPOs are processed. This behavior can be bypassed using the GPO setting found at Computer Configuration\Administrative Templates\System\Logon\Always wait for the network at computer startup and logon. So, startup scripts will run after computer preferences but before user preferences and login scripts will occur after all preferences have been set. Hope that helps.

Order is set by the admin with the setting with teh lowest link order processed last (thus having the highest precedence). If you need to ensure that policies are applied at boot use the setting Computer Configuration\Administrative Templates\System\Logon\Always wait for the network at computer startup and logon. Also set Apply Group Policy for computers synchronously during startup. This forces the system to wait until it can retrieve and process computer policy before allowing the user to login. If you need to check if group policy ran sucessfully check the log files listed here