On Ubuntu (11.10 and 12.04), vim is not installed, but “vim.tiny” instead. “vim.tiny” doesn't support command history!
Also: vi is a redirect to vim.tiny, thru the update-alternatives mechanism.
$ ls -al `which vim.tiny` `which vi` lrwxrwxrwx 1 root root 20 2012-04-10 10:06 /usr/bin/vi -> /etc/alternatives/vi -rwxr-xr-x 1 root root 713312 2012-02-28 05:53 /usr/bin/vim.tiny
so, apt-cache search vim | grep vim and sudo apt-get install vim. Once installed, “vi” points to “vim.basic”, again by the alternatives mechanism.
# /usr/bin lrwxrwxrwx 1 root root 20 2012-10-12 00:37 vi -> /etc/alternatives/vi lrwxrwxrwx 1 root root 21 2012-10-12 00:37 vim -> /etc/alternatives/vim -rwxr-xr-x 1 root root 1883196 2012-02-28 05:53 vim.basic lrwxrwxrwx 1 root root 25 2012-10-12 00:37 vimdiff -> /etc/alternatives/vimdiff -rwxr-xr-x 1 root root 713312 2012-02-28 05:53 vim.tiny -rwxr-xr-x 1 root root 2084 2012-02-28 05:51 vimtutor
# /etc/alternatives/ lrwxrwxrwx 1 root root 18 2012-10-12 00:37 vi -> /usr/bin/vim.basic* lrwxrwxrwx 1 root root 18 2012-10-12 00:37 vim -> /usr/bin/vim.basic* lrwxrwxrwx 1 root root 18 2012-10-12 00:37 vimdiff -> /usr/bin/vim.basic
in summery, there's binaries vim.tiny and vim.basic. By default, Ubuntu only has vim.tiny. The command name points to vim.tiny. After you install vim, the command name vi or vim point to vim.basic. They point by mechanism of the update-alternatives (which is basically round-about soft links.)
also, the whole vim install (which includes docs) is now a whopping 29 MB. Ha, still only 1/5 of emacs! 〔☛ Xah Emacs Tutorial〕
For a basic vim tutorial, see: Emergency vi (vi tutorial)