It's a multistep process best done by following the installation instruction on Joomla's web site. In short: 1) Create a database on your web server 2) copy the files to your server 3) open your site in the browser and fix the errors it tells you about 4) Continue the setup after all the errors are cleared. 5) Delete the installation folder Thats a quick summary. The key here is that it must be installed on a server that uses PHP/MySQL.
If your hosting plan has Fantastico, you can install it through there. It's not the best solution since they may not have the most up to date version, but it's easy. Better to use the manual method though.
I use Hosting Zoom and Hostgator, and find them both to be reliable and stable. I tried going with some of the smaller hosting companies for a while, but I had too many problems, so now I'm trying to stick with the bigger guys. There are many options out there depending on your budget, these are my two choices. Be careful of anyone who is offering you unlimited space or bandwidth though, this can lead to lots of headaches down the line. Go for a reliable host with a good history that is within your budget.