An AnonymousProxy service allows for greater privacy on the internet, and is marketed chiefly at the more rabid species of CryptoNaut. All users of an anonymous proxy service share the same IP address (or address range).
While they allow for PlausibleDeniability, they typically fall to law enforcement in due course. In many countries such services are now required to keep logs and make them available to police. Even for the short lived anonymous proxies, governments that want to attack the use of anonymous proxies can simply create a PhonyFlood of HoneyPots (e.g. [1]). That is, just like the war on drugs, if the government is the main supplier, the government has a good chance of finding the users.
Many sites (including WikiPedia) block all anonymous proxy services as they discover about them, since anonymous proxies are often used in EditWars.
Anonymous proxies break down into a wider taxonomy, that can be described by how a few key HTTP header fields are munged. Note they cannot be reliably detected based on headers, as you will see.
Transparent Proxies.
Transparent proxies are simply proxies that do not hide the originator's address. Legitimate ones exist simply to help people speed up their Internet connections or to skirt firewalls and filters. An OpenProxy, however, may be a compromised machine.
Anonymous proxies.
These proxies announce loudly that they are hiding the user's address, perhaps because they are poorly designed, or perhaps as a form of CivilDisobedience? to inform webservers that people will not stand to have their privacy invaded. They simply replace your IP with their own. They identify themselves clearly by claiming they are a proxy acting on their own behalf (i.e. supplying their own IP).
Distorting proxies.
Again, these proxies make it clear that they are proxies, but they pretend to be transparent proxies by supplying an IP other than their own. These are rather insidious because they are difficult to distinguish from transparent proxies.
High anonymity proxies
These proxies pretend to be a person by making a separate connection with its own HTTP headers, without supplying proxy headers. These are perhaps the easiest to write for simple applications, as it just requires channeling data from one connection to another. They are also not detectable from headers.
Web-based proxy.
Aside from an OpenProxy, many commercial providers offer anonymizing services through CGI-based forms. While any of the above types of proxies can be channeled through CGI, it serves to mention CGI-based proxies separately since they are frequently used by novice attackers and vandals. These commercial proxies are easy to use since they require little technical knowledge except for the fact that they exist and the ability to use Google to find them, and similarly it is easy to ban them since there are so few. A naive list of regexes for popular CGI-based proxies is available from the local BanList. Unfortunately, it is harder to automatically detect non-commercial "underground" CGI proxies. Unlike an OpenProxy they do not have an simple and standard MachineInterface to access them.