11月2日現在ではCentOS 5.4でyum install yum-prioritiesとしてもインストールできません。
CentOS5.4のリポジトリから漏れてしまっているだけで、CentOS5.3のものをインストールすれば良いようです。
# wget -c http://mirror.centos.org/centos-5/5.3/os/i386/CentOS/yum-priorities-1.1.16-13.el5.centos.noarch.rpm
# rpm -ivh yum-priorities-1.1.16-13.el5.centos.noarch.rpm
または
# rpm -ivh http://mirror.centos.org/centos-5/5.3/os/i386/CentOS/yum-priorities-1.1.16-13.el5.centos.noarch.rpm
http://lists.centos.org/pipermail/centos/2009-October/084246.html
(追記)
11月12日現在では、[extras]リポジトリに追加されていました。
yumの設定がデフォルトのままであれば、5.3までと同様にインストールできるようになっています。