I work for a college with almost a thousand users (faculty and staff). Many staff members also teach part-time, and many faculty members teach in different departments.
Knowing that a user and/or computer can only exist in a single OU, what kind of strategy would allow for a nice hierarchical structure, and still be flexible enough to allow different department Group Policies to apply to the same user.
This can't be too uncommon of a scenario but I'm just not seeing the simplest or cleanest layout yet.
Without some explanation of the specific scenarios you're looking for it's difficult to give you any "step by step".
User Group Policy application is influenced by:
Those are all the mechanisms for controlling user Group Policy application. Between all those functions you can create reasonably complex deployment scenarios.
Your OU hierarchy should always be designed first based on planned delegation of control. You only get one OU hierarchy and there are no good mechanisms to decouple delegation of control from the OU hierarchy. Design for delegation of control first, Group Policy application second.
I focus on using security group membership to filter user Group Policy application. Never forget that some settings within GPOs have ACLs separate from the GPO itself. The "Block Inheritance" and "Enforced" / "No Override" functions should be used sparingly and are typically indicative of a broken design. Loopback Group Policy Processing can be a very powerful and useful tool, but it's a bit complex to understand.
You're focusing on users but I'll take a moment to mention computers, too. Computer Group Policy application has all the same filtering functionality as user Group Policy, but also includes WMI Filtering. WMI Filtering can let you target GPOs to specific hardware or operating system-related attributes of computers. I often see security group filtering neglected when filtering computer Group Policy.
There are some things you can accomplish with both WMI Filtering and security group filtering for computer Group Policy. WMI Filtering has the added feature of being dynamically calculated on each Group Policy application (versus security group memberships, which must be changed manually to affect filtering). Security group filtering can still be beneficial if you have computers located in disparate OUs without a WMI filterable attribute that need to have common Group Policy Objects applied. I use security group filtering with computers, frequently, to control Software Installation policy (wherein I have a GPO with multiple software packages assigned, each with a unique ACL that includes a group to control the software installation).
The most important thing you can do, setting aside everything I said above, is to make sure you fully understand how the Group Policy client calculates the Resultant Set of Policy and, with that knowledge, brainstorm and test possible designs before putting them into production. I firmly believe that testing should start with pen and paper (whiteboard, etc) rather than software. You need to have enough organizational knowledge to be able to design realistic scenarios and test them. Get other groups in your IT organization (and outside the IT organization if need be) involved. Your Helpdesk team, for example, will have delegation of control needs that will drive the physical OU hierarchy. Your desktop support team may have software installation needs that drive computer group policy filtering. There are any number of possible scenarios that should be talked through, worked out on paper, and finally tested in a lab scenario before being put into production.