Problem:
You’re using latex or pdflatex to compile a .tex file, but you get an error message similar to this one (the solution will work for any missing file, not just utf8x.def):
! LaTeX Error: File `utf8x.def' not found.
Now you’re wondering which package you need to install
Solution 1: Install everything
This problem can often be fixed once and for all by just installing all packages:
sudo apt-get install texlive-full
However, this pulls in a huge amount of packages and is therefore not recommended for most situations.
Solution 2: Install only required package
You can use apt-file to find the package containing the missing file and install it.
First, update the list of files in all known packages (sudo apt-get install apt-file if required):
sudo apt-file update
You only need to do this once every few months or so, before you use apt-file.
Then, look for the missing file (replace utf8x.def by your missing file):
$ apt-file search utf8x.def texlive-lang-japanese: /usr/share/texlive/texmf-dist/tex/latex/bxbase/bxutf8x.def texlive-latex-extra: /usr/share/texlive/texmf-dist/tex/latex/ucs/utf8x.def texlive-luatex: /usr/share/texlive/texmf-dist/tex/lualatex/luainputenc/lutf8x.def
Now it takes some educated guessing which of the three listed packages (texlive-lang-japanese, texlive-latex-extra, texlive-luatex) needs to be installed. In this case, texlive-latex-extrais the correct choice as the other packages list the missing file only in some subdirectory of package (like luainputenc). If in doubt, you can just install all of the listed packages.