Mage::throwException is used to throw exceptions of the specific
Mage_Core_Exception variety. These are generally used to present error messages to the end user. For examples of this, do a quick search for
Mage::throwException in the Mage_Checkout module, you'll find many instances where the error message is actually being translated before it's thrown, as it's ultimately going to be added to the session object and displayed to the user on the resulting page.
new Exception or something like
new My_Custom_Exception would normally be where you are throwing errors internal to the application, errors which most likely should never be displayed to the end user. Maybe you catch these and handle them gracefully (good use for a custom exception type in some cases), or other times they end out caught, logged and terminate the request with a more generic error message being displayed to the user.
I've never personally used
Mage::exception but it appears to be an attempt to pattern having a unique exception type for each module. There would be no harm done in using it, as it is essentially a factory which returns an exception instance for the given module, although (at the time of this writing) it does not implement any support for such things as overrides.
grep -r throwException /path/to/magento/app/code/core | wc -l ; grep -r throw\ new /path/to/magento/app/code/core | wc -l ; grep -r throw\ Mage /path/to/magento/app/code/core | wc -l- though that requires that you know what too look for.