Tested on: Linux Mint 17.1 Rebecca (Ubuntu 14.04 LTS - Trusty Tahr)
This error with pdflatex has been mystery to me for a long time. Surprisingly, it is not easy to find a clear solution online.
Installation of the package pgf is the most important bit! Without pgf LaTeX will keep complaining that tikz.sty is missing. This solution was also proposed in a comment on stackexchange:
This error with pdflatex has been mystery to me for a long time. Surprisingly, it is not easy to find a clear solution online.
ERROR: LaTeX Error: File `tikz.sty' not found.
--- TeX said ---
Type X to quit or <RETURN> to proceed,
or enter new name. (Default extension: sty)
Solution
sudo apt-get install texlive-pictures pgf
Installation of the package pgf is the most important bit! Without pgf LaTeX will keep complaining that tikz.sty is missing. This solution was also proposed in a comment on stackexchange:
... The pgf package, as I keep forgetting and remembering every year, is independently installed from the pictures (which includes tikz but it's not loaded unless pgf is present) extras, the common, and the main tex on 'ix systems.