How does Versions work with iCloud?
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.