Gaim is the default redhat IM program...and, hey, look at that, it does ICQ too 🙂
What you need to do is click the plugins button when it first comes up, and then hit the load button, up pops a list of all the plugin files....find the one that says ICQ and load it (as well as any others you want, gaim does MSN, Yahoo, IRC and jabber as well). Then create a new connection and in the type dropdown box pick the one that says ICQ. Type in your ICQ User ID number, and password, and away you go.
Note: This might not be exactly how its done...as I'm not infront of my linux box right now.