The accepted answer answered my question at the time, but is now outdated. Back then grunt-cli used grunt, but with another branch. The not-accepted answers will tell you how it is today.
What is the relations and differences between grunt-cli and grunt? It seems to be the same thing, but different versions.
https://npmjs.org/package/grunt
https://github.com/gruntjs/grunt
https://npmjs.org/package/grunt-cli
https://github.com/gruntjs/grunt/blob/devel/docs/getting_started.md
You're correct, the two projects exist because of different versions of grunt.
grunt-cli is used for grunt version 0.4 (and has an explicit dependency on 0.4), which as of this writing is in alpha development. grunt-0.4 splits the command line interface (grunt-cli) from the API libraries.
The "Getting Started" documentation you found is in the devel branch of the grunt repository, which will be the 0.4 release.
If you're using grunt 0.3.x, then you don't need to install grunt-cli.
As far as I know, grunt-cli is simply a tool to access Grunt from command line anywhere in the system, but it doesn't include Grunt itself. In other words, Grunt-CLI only looks for locally installed Grunt files somewhere in the filesystem, but it doesn't have the functionality of the regular Grunt.
From: http://gruntjs.com/getting-started
Install grunt-cli just will put the grunt command in your system path, allowing it to be run from any directory.
Even more:
...Installing grunt-cli does not install the Grunt task runner! The job of the Grunt CLI is simple: run the version of Grunt which has been installed next to a Gruntfile. This allows multiple versions of Grunt to be installed on the same machine simultaneously.