>>> I'm not sure how new users are supposed to find evince.
The command line is my choice as well. I have a tiny shell script that gets run after each update that creates text files of whats installed and available:
$ cat upd.sh
yum list installed 2>&1>yum.installed
yum list available 2>&1>yum.available
then its just a matter of
grep some_program_or_other yum.*