Cannot decompress .tar.xz file, getting "xz: Cannot exec: No such file or directory" from tar

Per How do I uncompress a tarball that uses .xz?, I tried tar xf php-5.6.0RC4.tar.xz and tar -xJf php-5.6.0RC4.tar.xz and in both cases I get the following:

tar (child): xz: Cannot exec: No such file or directory
tar (child): Error is not recoverable: exiting now
tar: Child returned status 2
tar: Error is not recoverable: exiting now

It's this php-5.6.0RC4.tar.xz.

I'm running Ubuntu 14.04 LTS.

What's wrong?

The line

tar (child): xz: Cannot exec: No such file or directory

gives you the real error. The xz programm cannot be executed, probably because it is not installed. To install the xz (de)compression tools, issue one of the following commands depending on your distibution:

sudo apt-get install xz-utils          # Debian / Ubuntu
sudo yum install xz                    # RHEL / CentOS
sudo zypper in xz                      # OpenSuSE
sudo pacman -S xz                      # Arch Linux