The first stop for Linux applications always has to be your distribution's package manager. Almost every distribution today includes a package manager. This tool allows for the installation/uninstallation/clean-up of applications in your Linux install. These package managers (yum, synaptic, portage, etc) are incredibly versatile applications which check for dependencies, reverse dependencies, version mismatches, best installation environments and many other things to install the application in the best way possible.
These package managers work with repositories (servers where applications and metadata are stored) and install applications. All the distros which include a package manager host their own repositories of applications which are modified and tested to work best on their own distribution. Ubuntu has its own software repositories, Fedora Core has them too, and so do most other distributions being used today. These repositories, or shortened to repos, contain a wealth of applications for every purpose. Since your package manager is very closely integrated into your distribution, the best way to install applications in Linux is through the package manager. Please refer to your distribution's documentation for how to use your package manager.