As long as you are not using the educational version and you are not reselling the program or part of the program, then I don't believe it is a problem. People create howtos and tutorials all the time.
If you are going to be earning money with this and haven't set up a business before, I'd recommend consulting a lawyer to cover *all* your bases (there are more than just copyright issues to be concerned about). At the very least sit down with somebody who has done this in your region to ensure you aren't missing anything important.
Thanks for the quick reply everyone. As stated, yes I'm selling the video tutorials.
My version of Maya and Mudbox are both commercial versions since I work as a freelancer anyway.
In terms of finding someone who has done this in my region (Australia) I have searched before and have found none so I figured here would be better.
The video tutorials are almost done, my business is set up with the essentials but as you said, legally I will need to further my research. There's so much in legal that makes my brain explode.
Keep the posts coming while I keep asking around.