What you want to do is possible, and should be particularly easy with Internet Connection Sharing, but obviously you haven't had much luck.
The first thing to do is to reboot the Linux machine if you haven't already. Next, if it still doesn't connect to the Internet, you'll need to review the network settings. The Linux machine should be set up to get an IP address automatically-I don't know the terminology Red Hat uses for this. Neither do I know what desktop environment you have installed, so there are a lot of possibilities for where to look, what things will say, etc.
At least that's a starting point...