It actually is installed on Ubuntu but for some reason it’s not put anyplace where git can find it. Easiest way is to create a symlink:
sudo chmod +x /usr/share/doc/git/contrib/subtree/git-subtree.sh
sudo ln -s /usr/share/doc/git/contrib/subtree/git-subtree.sh /usr/lib/git-core/git-subtree
UPDATE 1: looks like a patch has been submitted upstream to fix this but it hasn’t yet been merged.
UPDATE 2: the patch to fix this in Debian has been merged, but since they went the route of a separate git-subtree package I don’t think this will make it to Ubuntu 12.04. Seems to not be an issue in 14.04 as /usr/lib/git-core/git-subtree is already created correctly by the git package.