If you're using the default for Red Hat 8.0, then you're in Gnome, and I think you're using MetaCity. Anyway, that what I've got (the default). The links you're talking about are called "Launchers". Right-click on your desktop, choose "New Launcher", and fill in the edit boxes.
You may want a terminal open to verify the path to the program by typing 'which gaim'. Then click the box for the icon to choose what the Launcher will look like, and you're done.