I've done some testing, and can offer a (hopefully) authoritative answer.
Short answer: the versions are stored on the same disk (or disk image) as the actual file, so versions shouldn't leak information outside of your encrypted image. But there might be another leak, see below.
Long answer: Versions creates an invisible folder at the top of each volume, named ".DocumentRevisions-V100" with an internal structure like this:
.DocumentRevisions-V100
.cs
ChunkStorage (this is presumably used to store chunks of large files that didn't entirely change between versions)
AllUIDs (this is only created on disks that have permissions ignored)
ChunkTemp
db-v1
db.sqlite (this is the primary index of document IDs, etc)
PerUID (this is only created on disks that have ownership respected)
501 (documents created/owned by user #501)
502 (etc...)
staging (???)
For info on the sqlite index and the background daemon that mediates access to it, read John Siracusa's excellent review at ars technica.
The document versions themselves are stored in subdirectories in either AllUIDs or PerUID/youruserid. Under that, each versioned document gets its own subdirectory, numbered starting at 1. Under that is a single folder named "com.apple.documentVersions", and under that, each revision is stored as a separate document (unless it's broken into chunks -- I haven't experimented with large documents) named with a UUID and type extension. For example, if I (user #501) edit a rtf document on my boot volume and save several revisions, they might be stored as:
/.DocumentRevisions-V100/PerUID/501/1/com.apple.documentVersions/0787B7C3-DE11-4065-9FD9-61870212011D.rtf
/.DocumentRevisions-V100/PerUID/501/1/com.apple.documentVersions/D533CF36-0D49-4910-B0EB-C92395C05726.rtf
If I then opened another rtf file and saved a version of it, it might be named:
/.DocumentRevisions-V100/PerUID/501/2/com.apple.documentVersions/74A6EF6E-A22A-4196-B560-40ABDBF46DF4.rtf
If I saved it on my SecretDocs image (mounted with ownership ignored), versions would be stored like:
/Volumes/SecretDocs/.DocumentRevisions-V100/AllUIDs/1/com.apple.documentVersions/2ED4DAFD-9BCF-4158-BFDB-F9EEC631E44A.rtf
BTW, permissions on the version files seem to be cloned from the original files. Permissions on the enclosing folders tend to allow execute only (i.e. you can't see the filenames, but if you know the file's name you can access it). For example PerUID/501 is set to allow execute only for user 501, no access for anyone else. The db-v1 folder only allows root access. Without investigating in detail, it seems to be pretty locked-down.
Now, about that other leak I threatened you with: Lion apps tend to save their state when you quit, so if you have a confidential document open when you quit, some of its information (like I think a screenshot) may get stored in ~/Library/Saved Application State/someappid.savedState. As long as you close before saving I think you're safe here.
iCloud itself does support document revisions, and my understanding is that it does the same job OS X does for versions stored locally (keeps track of all the small changes, and is in charge of assembling all the chunks into different versions). So any OS X app that supports versioning and iCloud storage should handle both together seamlessly, the same as if it's stored locally. It sounds like you're seeing the expected results in this case.
On iOS it's a bit more complicated - apps have access to other revisions of the document, but because there's no standard way for a user to see different versions (as in OS X), it's up to the app developer to deal with this. I believe the recommended practice for iOS apps is to only keep versions as necessary (for example, dealing with two conflicting versions).
Based on my understanding, if you create a document on iOS, then edit it on OS X, you should be able to view the revisions on OS X, but iOS will only show the "current" one, and OS X will probably only include one iOS-edited version of the file, with whatever versions were edited on OS X. However, this all depends a lot on how the iOS developer implements iCloud storage, and based on my reading of the developer documentation, if an iOS app has what it can satisfactorily decide is the canonical up-to-date version of a document, it may discard all previous versions. That may be why you were running into issues with iOS-created Pages documents.
Ultimately, iCloud is a pretty complex thing, and while they go to great lengths to make it seem simple for the user, some of that complexity can get in the way.
TL;DR version: using OS X only, versions should sync fine. Bringing iOS into the mix can change things depending on the developer's implementation.
Best Answer
Good news. After some prompting over in the Apple support forums and experimentation, I've discovered that the "close and revert" option does not do what it says. In fact it closes the document without touching the file on disk - exactly what I'm after!
To recap, when closing a modified file that supports Versions, this dialog appears:
There does not appear to be an option to close without changing what's on disk. However, the Revert Changes button actually behaves like a Don't Save button, leaving the file on disk untouched.
This is precisely the behaviour I need to support the case where the file on disk has been modified by another application and I want to preserve those changes.
As made clear in the Apple thread, this is all probably subject to change and may be fragile, but for now I have a solution.