You can easily add a theme if you have FTP access to the themes folder of your Drupal installation.

Finding themes is easy too - you can Google'Drupal Themes' and come up with a wide selection.

Or you can go to http://drupal.org/project/Themes for Drupal's listing

Or you can go to http://themegarden.org/drupal50/ a site that has many themes.

Things to beware

• Make sure your theme matches your Drupal version. 4.x themes will not work with Drupal 5 
• Go to sites that use the theme. Sometimes themes look OK in a screenshot but fall apart in the real world.
• Even if a theme works OK, try using it to administer your site, or adding content to see how it behaves.