Short: To update your TEXMF database run
I would always install packages from CTAN, e.g.
http://www.ctan.org/tex-archive/macros/latex/contrib/xcolor, in the case of
xcolor, but the author's website is of course also fine.
The README file contains installation instructions:
Extract all package files:
Put the generated files to their respective locations
within the TeX installation:
*.sty -> /tex/latex/xcolor/
*.def -> /tex/latex/xcolor/
*.pro -> /dvips/xcolor/
Create the documentation:
`makeindex -s gind.ist xcolor.idx'
Run the test files (N=1,2,...):
However, TeX Live comes with a package manager called
tlmgr (not included in the version delivered by Ubuntu or Debian). With this manager you can install
xcolor simply using:
tlmgr install xcolor
Which will update the database as well. Note that you can update all installed packages using:
tlmgr update --self --all
I personally would simply install the full TeX Live (if you have the HD space of ~2.5GB) using:
tlmgr install scheme-full
Then you don't have these issue any longer.