Yes, documentation and best practice is a bit scarce on this. We’ll have more eventually (also talks etc).
You can see some existing applications of certified data:
- The Internet Identity canister uses Canister Signatures (also explained in the Interface Spec) using this code: https://github.com/dfinity/internet-identity/blob/main/src/internet_identity/src/signature_map.rs
- Similarly, there is code in the Internet Identity related to HTTP certification: https://github.com/dfinity/internet-identity/blob/0f1620b712c1a23f7d70580852d99d72366c6c76/src/internet_identity/src/main.rs#L789
- The registry canister certifies it’s responses: https://github.com/dfinity/ic/blob/024de2fc73d7f6f5df5a92edf9675851f9ebbf59/rs/registry/canister/canister/canister.rs#L482
- As does the ledger, which simply puts the hash of the latest block into it: https://github.com/dfinity/ic/blob/779549eccfcf61ac702dfc2ee6d76ffdc2db1f7f/rs/rosetta-api/ledger_canister/src/main.rs#L77
- Not published yet, but a new asset canister is shipped with latest
dfxthat certifies its assets. - Related: A motoko library for such a hash tree: https://github.com/nomeata/motoko-merkle-tree
My takeaway is that CertifiedData is meant to be the source of verifiability at canister level. It could be a merkle root I guess? Or maybe the hash of latest “block” of a canister owned blockchain?
Yes! The canister can choose, and as you see in the examples above, both are valid approaches.
I’d like to add that, I’m most interested in the recommended implementation of such mechanism in the most cycle-efficient way. Currently I don’t see any material about estimating cycle consumption.
I don’t know if I know the most cycle-efficient way; at this point I am already happy when it works 
Unless you have very special needs, I’d recommend to use the same hash tree representation as the system itself (see Interface Space). This is also used by all the above applications, except the ledger, and you get to re-use some libraries, e.g. https://github.com/dfinity/agent-rs/blob/next/ic-types/src/hash_tree.rs and https://github.com/dfinity/internet-identity/tree/main/src/certified_map (which I personally hope will eventually be available separately, with a more liberal license, and on crates.io).
Using the rbtree, or a similar datastructure (e.g. a patricia trie as in the case of the Motoko library) will only recompute few hashes as you change the data structure, and give you decent cycle consumption. There can always be more optimizations, of course.