Rooting your phone, in and of itself, is not illegal (although, there have been some issues surrounding jailbreaking of iPhones...but that's a whole other discussion). Android as a platform is open source and installing a custom mod, or messing around with the internals of the operating system isn't a problem.
Now, as you pointed out in your comment to Bryan's post, there is some software that is licensed. As such, you are governed by the license that you agreed to for those applications (typically through purchase of the phone).
The real legal ramifications that come up would revolve around what it is that you do with your phone once it is rooted. Some would argue (and I don't necessarily agree) that using tethering with a rooted phone is illegal because you haven't paid for it (of course you have paid for the data...but...again, I digress). The phone service providers would most likely tell you its all illegal because they want to lock you in. By locking you in, they guarantee a revenue stream.
So, all-in-all, I don't particularly see a problem. However, I am not a lawyer, so I would ask one if you are truly concerned about the issue.