1) Install latest version of Rust found here: http://www.rust-lang.org
2) git clone --recursive git@github.com:rust-lang/cargo.git
3) make
4) make install (could be that sudo is needed for you)
Hmm, well, rust's brew seems a little outdated (0.10), so if you are intent on using Cargo soon, I would recommend on building rust yourself or grabbing a new binary from their website.
Stuff being either in Cask or Homebrew is just terrible. Homebrew also has a versions tap. Those two projects should combine efforts and remove ambiguity.
Yesterday started my contract with Mozilla to write documentation. Today, I'm starting on re-writing the tutorial: https://github.com/rust-lang/rust/pull/15131 (apparently, bors is a bit backed up)
The new tutorial will be based around 'real' Rust development, and so will assume Cargo.
That said, http://crates.io/ should have install instructions on the site. I'll open a ticket and get on that.