I'll leave legality to someone else. In terms of how they do it, here's a rough overview:
- Any connection, encrypted or not, is visible to your ISPs routers as a TCP session (generalization, I know there are other protocols).
- The routers know, regardless of whether or not encryption is present, how long each session has been connected for, and how much traffic has been processed.
- Session length and traffic per session are key metrics used for bandwidth management - there is normally a limit to the total number of sessions/connections, and also data rate per session. There may also be an "allowance" of unthrottled data per TCP session, so that web pages (even HTTPS ones) continue to load quickly.
- In addition to the rough throttling methods below, various companies are able to distinguish between web traffic, VoIP, torrents using clever heuristic methods, thus allowing for particular applications to be selectively throttled.
There are a number of ways to reduce throughput, but many just use TCPs inbuilt congestion control mechanisms. The bandwith management appliances will start dropping packets and/or increasing latency on those TCP connections that need to be slowed down. These will be interpreted by the TCP protocol as congestion, and result in a speed reduction. Again, this is very greatly simplified!
You can bypass most application detection using a VPN, but it will still be subject to the basic controls described in #3.
Most good bandwidth management solutions is not impede HTTPS websites, yet still detect and throttle file sharing connections.