Ok firstly, your question about packages, basically yum is a program that interfaces with a database of packages and their dependencies (called a repository), that various wonderful people have setup and maintain for whatever reason. When you run the yum commands they are querying/contacting these repositories to get information on the packages (well their headers, to show whats available), and any others that are needed in order to resolve the dependencies of what you want. I
The reason the packages aren't on your system is because not everyone wants them, so by using Yum people have the choice of what they want, not things stuffed down their necks, but access to anything extra they need. Also saving muchio spacio
As for your particular problem, when you do yum install <package> it's querying your listed repositories (/etc/yum.repos.d/<repos> - take a look to better understand, following that faq you may have entered them into/etc/yum.conf
Now the search string you gave is quite specific, if you get no luck with a search, try and broaden it (likewise if you get too many, try and refine it).
I checked yum for gstreamer and got these packages listed:
That should do you. Of course i usually find the easiest way is using xmms with the xmms-mp3 plugin from yum, however i suspect you are going for Amarok, which i find a much superior player