You can use "mail-notification" for GNOME, which is available on Fedora through yum. I have version 4.0 on x86_64, it supports Gmail natively (ie. you don't have to worry about checking your Gmail through POP). So after you:
yum install mail-notification
You can invoke it with the command "mail-notification", and configure at least one e-mail account.
To have it start automatically, go to System -> Preferences -> More Preferences -> Sessions, then under Startup Programs, add "mail-notification".