You can download a new theme from the
official Magento
web site. So far there is one available Magento theme
and its announcement is published at:
http://www.magentocommerce.com/boards/viewthread/568/
Once you download the theme, please uncompress it and
upload the theme and the Skin
folders of the Magento installation through
FTP
under the corresponding locations:
your_magento_folder/app/design/frontend/default/
and
your_magento_folder/skin/frontend/default/
Then rename the two folders to match.
In this example we will install the Tealo theme.
The folders are called tealo-theme
and tealo-skin. We have
uploaded them to the respective locations and renamed both
of them to tealo.
Since the script installation was performed in the
public_html/magento folder, the
corresponding locations are:
public_html/magento/app/design/frontend/default/tealo/
and
public_html/magento/skin/frontend/default/tealo/
Once the folders are uploaded, navigate to your
Magento admin area -> System -> Configuration -> Design.
Click on the Themes option and enter the theme name
in the Default, Layout, Templates and
Skin fields.

Click on the [Save] button and your new Magento
theme will be installed.