A proxy server is a server that allows clients to connect to the internet through a another machine on the local network (or on the internet).
A common usage of a proxy server is for caching, like Squid proxy. This allows a faster and more reliable connection to the internet and allows logging and filtering by the admin, which is used to combat inappropriate usage, viruses, spam, etc. It can, however, be used to invade user's privacy.
Another use of proxies is to circumvent such censoring and monitoring measures. This is accomplished by a user who is inside the censoring firewall connecting to an outside proxy that is not currently on the firewall's blacklist. This connection is often encrypted. An example of such a proxy service is http://www.anonymizer.com . These kinds of proxies are often used by Chinese citizens who wish to gain access to pornography, international news, and other contraband information while behind the Great Firewall of China. There is an arms race to create proxies faster than the administrators of the Great Firewall can ban them.