A proxy server is simply a server that receives requests from clients (most of the time we're talking about HTTP proxies and web browsers are the clients), and then forwards them on to the destination (and acts as a proxy between the client and destination).
There are many benefits to a proxy server, the least of which is the privacy benefit people above talked about. Most proxies have a caching feature, so that when someone views a web site, that page gets put in a cache on the proxy server and when someone else goes to get that page, the proxy server pulls from it's cache instead of making the request to the real server (speeds up page load times). A proxy server can also filter web requests, by only allowing requests to certain websites or alternatively blocking requests to certain websites.
Using a proxy server is completely legal. to use one, you just need to first find a proxy server you can use, then configure your web browser to use that proxy server.
For Internet Explorer:
http://support.microsoft.com/kb/135982
For Firefox:
http://www.healthsystem.virginia.edu/internet/library/services/computing/proxy-firefox.cfm