Users can not access web pages once signed onto internet

My users can sign on to AOL but when they go to search a web site they can not. They get an offline web page not available screen.

If I change their rights to Administrator then full web access is available. That defeats my purpose. How do I leave them as a User but they are able to search the web.

Please email me direct using the subjectline Windows 2000 user problem. this way it won't go into the spam file