How do I install new packages on Texmaker? I use Ubuntu 10.04 LTS.
You've got some options.
The easy and consistent way is to use your Ubuntu package manager, Synaptic or Ubuntu Software Center. The Ubuntu repositories contain TeX Live bundles, but their names often don't match a specific package. So, use the search feature to search the package descriptions for the package name. Click to choose and install.
You could install (extract, copy) the package into your user home directory, to ~/texmf. This is an option if Ubuntu really doesn't provide it or if you would like to use a newer version. In that case, download it from http://ctan.org/pkg/packagename. There are often installation instructions available. On this site, you could additionally check questions regarding installation of packages in general.
If you want to use the latest version of TeX Live, newer than Ubuntu provides and with its own package management, you could install the original TeX Live. Visit http://tug.org/texlive/. You might also read How to install “vanilla” TeXLive on Debian or Ubuntu.
You may follow the suggestions in this post.
After all, it's independent of Texmaker.