I have a Windows service A that depends on service B.
According to this Microsoft KB article I can add a registry key to tell Windows to wait until B starts before starting A.
Can I therefore expect service A to be shut down before B when I shut down Windows?
Unfortunately not prior to Windows Vista.
Here's the word from the horse's mouth: http://support.microsoft.com/kb/203878
Windows Vista (and newer versions) have a "Service Shutdown Ordering" feature. This is controlled by the "PreShutDownOrder" registry value (briefly mentioned in http://technet.microsoft.com/en-us/magazine/2007.03.vistakernel.aspx).
Searching "PreShutDownOrder" with "site:microsoft.com" on Google is returning an unhelpfully low number of results. It looks like it's only quasi-documented by Microsoft. I'd play around with it and see if it does what you want.
Here's a blog entry that mentions it from the "Ask Perf" blog (a really great blog, BTW, if you like knowing about Windows innards): https://techcommunity.microsoft.com/t5/Ask-The-Performance-Team/WS2008-Service-Shutdown-and-Crash-Handling/ba-p/372708
A service who has other services depedent on it shuts down the other services before shutting it self when you do it manually.
Edit: Evan Anderson posted a link about it not using depdencies when shutting down the OS in case of running on UPS etc. It's a good and valid point (allthough it doesnt mention Windows newer than 2000.)