On Scientific Linux 6.3 works using terminus-fonts-4.30-1.el6 from sl repo and st-0.1.1-1.fc14.i686 from koji.

Show the follow errors on SL6.3: 

st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3
st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3

BUT! start and work fine. On Fedora 18 Alpha show similar error but no start never finalizing with: Can't load font -*-terminus-medium-*-*-*-16-*-*-*-*-*-iso10646-*

st is using the classic X11 bitmap fonts access that starts with searching fonts by the font mask which is on modern Xorg terribly slow especially with negative answer.

You have to install appropriate font (in your case it's Terminus font as you already found out) and encoding mappings (the remaining warnings) provided by xorg-x11-font-utils package.

(In reply to comment #2)
> st is using the classic X11 bitmap fonts access that starts with searching
> fonts by the font mask which is on modern Xorg terribly slow especially with
> negative answer.
> 
> You have to install appropriate font (in your case it's Terminus font as you
> already found out) and encoding mappings (the remaining warnings) provided
> by xorg-x11-font-utils package.

# yum install xorg-x11-font-utils
Loaded plugins: langpacks, presto, refresh-packagekit
Package 1:xorg-x11-font-utils-7.5-9.fc18.i686 already installed and latest version
Nothing to do

===============================================


yum install terminus-fonts.noarch terminus-fonts-console.noarch
Loaded plugins: langpacks, presto, refresh-packagekit
Package terminus-fonts-4.36-3.fc18.noarch already installed and latest version
Resolving Dependencies
--> Running transaction check
---> Package terminus-fonts-console.noarch 0:4.36-3.fc18 will be installed
--> Finished Dependency Resolution

Dependencies Resolved

=============================================================================================================================
 Package                                 Arch                    Version                       Repository               Size
=============================================================================================================================
Installing:                                                                                                                  
 terminus-fonts-console                  noarch                  4.36-3.fc18                   fedora                  675 k 
                                                                                                                             
Transaction Summary                                                                                                          
=============================================================================================================================
Install  1 Package

Total download size: 675 k
Installed size: 622 k
Is this ok [y/N]: y
Downloading Packages:
terminus-fonts-console-4.36-3.fc18.noarch.rpm                                                         | 675 kB  00:00:07     
Running Transaction Check
Running Transaction Test
Transaction Test Succeeded
Running Transaction
  Installing : terminus-fonts-console-4.36-3.fc18.noarch                                                                 1/1 
  Verifying  : terminus-fonts-console-4.36-3.fc18.noarch                                                                 1/1 

Installed:
  terminus-fonts-console.noarch 0:4.36-3.fc18                                                                                

Complete!


============================================================


After the installation of terminus-fonts-console st works!, thanks a lot, the message at start is:


st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3
st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3

But work fine, on CentOS 6.3 SL6.3 show the same message, but i guess it's ok

Installing terminus-fonts-console-4.36-3.fc18.noarch is solved, or works identical to CentOS 6.3.
I think that if terminus-fonts-console-4.36-3.fc18.noarch is a really necessary package for st, is very relevant make terminus-fonts-console-4.36-3.fc18.noarch as dependency of st, right?.

I don't think terminus-fonts-console is hard dependency. I believe you can ask st to use any font of your choice, thus this is not good idea.

OTOH the warnings about fontset are worth of investigation.

(In reply to comment #5)
> I don't think terminus-fonts-console is hard dependency. I believe you can
> ask st to use any font of your choice, thus this is not good idea.
> 
> OTOH the warnings about fontset are worth of investigation.

@Petr Pisar:

No a hard, but, if i no install terminus-fonts-console-4.36-3.fc18.noarch, st no work.
The warnings on terminal, are the same, identical of CentOS 6.3 and Scientific Linux 6.3 using gnome-terminal + st:

Scientific Linux 6.3 from gnome-terminal: st
st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3
st: missing fontset: JISX0201.1976-0
st: missing fontset: GB2312.1980-0
st: missing fontset: KSC5601.1987-0
st: missing fontset: JISX0208.1983-0
st: missing fontset: ISO8859-14
st: missing fontset: ISO8859-4
st: missing fontset: ISO8859-3

This message is a reminder that Fedora 18 is nearing its end of life.
Approximately 4 (four) weeks from now Fedora will stop maintaining
and issuing updates for Fedora 18. It is Fedora's policy to close all
bug reports from releases that are no longer maintained. At that time
this bug will be closed as WONTFIX if it remains open with a Fedora 
'version' of '18'.

Package Maintainer: If you wish for this bug to remain open because you
plan to fix it in a currently maintained version, simply change the 'version' 
to a later Fedora version prior to Fedora 18's end of life.

Thank you for reporting this issue and we are sorry that we may not be 
able to fix it before Fedora 18 is end of life. If you would still like 
to see this bug fixed and are able to reproduce it against a later version 
of Fedora, you are encouraged  change the 'version' to a later Fedora 
version prior to Fedora 18's end of life.

Although we aim to fix as many bugs as possible during every release's 
lifetime, sometimes those efforts are overtaken by events. Often a 
more recent Fedora release includes newer upstream software that fixes 
bugs or makes them obsolete.

Fedora 18 changed to end-of-life (EOL) status on 2014-01-14. Fedora 18 is
no longer maintained, which means that it will not receive any further
security or bug fix updates. As a result we are closing this bug.

If you can reproduce this bug against a currently maintained version of
Fedora please feel free to reopen this bug against that version. If you
are unable to reopen this bug, please file a new report against the
current release. If you experience problems, please add a comment to this
bug.

Thank you for reporting this bug and we are sorry it could not be fixed.