I had the same trouble. Fedora Core 2. Restoring a crashed RH 7.2. Used yum to install MySQL but could not get mysqld to start (file wasn't there). I messed with it for a few hours, even used the RPMs on the MySQL site (worked fine). I wanted a yum updateable version, so i googled and found your post
Anyway, more messing led me to find what a n00b i am (and i'm pointing my finger at you too!). Try this one:
yum -y install mysql-server
service mysqld start
"OK"
d'oh! Needed the other package... You'd think that would fall under the realm of "dependency" for the "mysql" package.