I've seen two approches to this problem...

1. Generic ID vs. Specific ID

   The principle here is that you still use whatever unique identifiers you would without versioning, and use those in whatever mapping tables / foreign keys you need -- call those your Specific IDs (specific to a particular version of the object). On top of that you have additional information that maps a Generic ID (generic for the object, regardless of version) to the currently "live" specific object, who has the generic checked out, etc.... Most of your clients will only ever use the Generic IDs, the only time any one ever needs to worry about a Specific ID is when they want to revert to a previous version, or make a "future" version "live"

2. Live tables vs Archive tables

   Again, use your normal schema with your normal unique IDs, but you add an additional "archival" table that flattens all of your data (maybe as an XML doc in a text field) and keeps track of the versioning info ... this is really only usefull for keeping a historic log. When making a new version, flatten the current one first and archive it. If anybody wants to "restore" an old version, de-flatten it.

Both methods have complexities. You have to think long and hard in advance about what makes up a single "object", what is it people "lock", how do you deal with related objects, and adding/removing/modifing relationships in different versions. As long as you do a good job of picking your rules in advance, either method can work.