You've got one good reply already, let me give it a shot too:
Tokio is an asynchronous IO stack for Rust. Like many frameworks/large libraries, you have to call things something. It's largely inspired by Finagle, and so shares some of its terminology, but not all of it, as Rust and Scala/Java are very different.
You can use futures without tokio. Futures are the lowest level of the stack: they give you a way to create a value that represents something "in the future". You make a future, it processes stuff in the background, and then you call a function to say "wait until the value is ready." You can do stuff in the meantime. It's not tied to IO or anything else, any kind of computation you want. It is mostly a very thin interface. I have a hobby OS project, and I'm considering making it "everything is a future".
mio is a thin abstraction over epoll/kqueue, and a slightly larger one over IOCP. That is, low-level asynchronous IO primitives.
tokio-core is futures + mio. That is, it takes the futures pattern and applies it to IO. It does this by adding an event loop, a "reactor core" (hence Core) that drives the futures along.
On top of that is tokio-proto. This lets you build protocols nicely on top of tokio-core.
This new package extracts out the main interface from tokio-core, so that if you wanted to, you could replace it with something else. Previously, you got these interfaces only from tokio-core, and so you had to depend on it to use them, which means you had to use only tokio-core. The idea with this package is that it gives you more composability; the interfaces are in here, so those working from above can use them, and then when you're building the stack, you can use tokio-core, or some other backend.
Finally, many people who use tokio won't actually use this directly: it's something other library authors build on top of. For example, hyper uses the tokio stack to do async HTTP requests. So most people don't even need to know or think about any of this. For example, I'm working on a little web framework on top of all of this, here's what it looks like to use: https://github.com/rust-lang-nursery/thanks/blob/master/src/... (this is _extremely_ small and a work in progress, don't expect Rails.) No need to look at or think any of that stuff.
As for examples, https://tokio.rs/docs/getting-started/tokio/ goes through the entire stack, bit by bit, building it up. It also links to a variety of other examples.