I did a bit more digging into Velocity last night. I still haven't written any code yet but I'm getting there!
I was poking around in the Object Browser at the System.Data.Caching namespace and I discovered that the context-sensitive help for each method is probably more helpful than the helpfile.
But more interesting than that, the help for Cache.Add(key As String, value As Object) suggests that if you call this particular overload, the item gets cached in the default region of the cache. Which raises all kinds of questions: if there is a region created by, well, default, which host is it tied to? Does the default region span hosts (in which case regions suddenly become a lot more appealing to me)? Can I use the default region everywhere?
Now I've got multiple instances, I can do a bit more experimentation with regions and see if they start to be a bit more useful, but I suspect my next course of action is to run ClientLibrary through Reflector and have a look at what Cache.Add actually does.