Proxy's themselves are not illegal. However, accessing a proxy server that you are not authorized to be on certainly is. Going out and finding a list of proxy servers and just deciding to log on means you know nothing about who owns it. Therefore determining if you are legal or not is impossible.
Some of the free proxy's are run by well meaning people who are just trying to make a buck. They get an internet connection, put up a proxy server, stuff it with pay for click ads and figure they will get rich. Unfortunately several things are working against them. First, bandwidth costs money and ads are not especially high paying. So they don't put a lot of bandwidth into the application. This means that your surfing is slow. Plus all those ads loading are both frustrating and add to the slowness. As with all proxy's they are easy to block and the owner soon realizes that his traffic has gone down and he isn't making any money. That ends the proxy service.
More worrisome are the free proxy's run by hackers who use them to infect your computer and in some cases even take it over so they can access the internet on your line. This allows them to do illegal stuff without it tracing back to them. The number of people getting all kinds of viruses and trojans after accessing a free proxy is quite high. In a lot of cases you don't even know it happened for days or weeks. In the mean time, they own you.
Another problem with proxy's is that they typically only work for surfing. If you need to access some other web service like SMTP mail, messenger programs, VOIP software and such you are out of luck with the proxy.
Read more on free proxy's below.