Note that Git 1.9/2.0 (Q1 2014) has removed that limitation.
See commit 82fba2b, from Nguyễn Thái Ngọc Duy (pclouds):
Now that git supports data transfer from or to a shallow clone, these limitations are not true anymore.
The documentation now reads:
--depth <depth>::
Create a 'shallow' clone with a history truncated to the specified number of revisions.
That stems from commits like 0d7d285, f2c681c, and c29a7b8 which support clone, send-pack /receive-pack with/from shallow clones.
smart-http now supports shallow fetch/clone too.
All the details are in "shallow.c: the 8 steps to select new commits for .git/shallow".
Update June 2015: Git 2.5 will even allow for fetching a single commit!
(Ultimate shallow case)
Update January 2016: Git 2.8 (Mach 2016) now documents officially the practice of getting a minimal history.
See commit 99487cf, commit 9cfde9e (30 Dec 2015), commit 9cfde9e (30 Dec 2015), commit bac5874 (29 Dec 2015), and commit 1de2e44 (28 Dec 2015) by Stephen P. Smith (``).
(Merged by Junio C Hamano -- gitster -- in commit 7e3e80a, 20 Jan 2016) 
This is "Documentation/user-manual.txt" 
A <<def_shallow_clone,shallow clone>> is created by specifying the git-clone --depth switch.
  The depth can later be changed with the git-fetch --depth switch, or full history restored with --unshallow.
Merging inside a <<def_shallow_clone,shallow clone>> will work as long as a merge base is in the recent history.
  Otherwise, it will be like merging unrelated histories and may have to result in huge conflicts.
  This limitation may make such a repository unsuitable to be used in merge based workflows.
Update 2020:
- git 2.11.1 introduced option git fetch --shallow-exclude=to prevent fetching all history
- git 2.11.1 introduced option git fetch --shallow-since=to prevent fetching old commits.
For more on the shallow clone update process, see "How to update a git shallow clone?".
As commented by Richard Michael:
to backfill history: git pull --unshallow
And Olle Härstedt adds in the comments:
To backfill part of the history: git fetch --depth=100.