What is the quickest way to check (on Linux) whether I already have a given package? In particular I'm interested in whether there is something that will take less time than the 20 seconds or so it would take me to create a tiny latex document and try to compile it.
kpsewhich pkgname.sty kpsewhich clsname.cls
The standard tool works not only on Linux but also on Windows systems: at the command prompt, the command
prints path and file name of one file
name.sty if it can be found, otherwise nothing.
kpsewhich -all name.sty
prints all occurences if there are several (try
kpsewhich -all texmf.cnf).
It uses ls-R files but could search the disk as well if you specify the option -must-exist. kpsewhich recognizes a lot of format names. Beside tex formats like .cls, .sty, .tex it finds font files, bib files and many more.
to learn more or have a look at this kpsewhich manpage.
This standalone program belongs to the kpathsea library. To read about it, type
at the command prompt. As you may know, texdoc is another very useful command for the shell.