- Install Tomcat 6.0, JDK 1.5 and MYSQL.
I'd advise not to purchase a plan that provides nothing but a bare-bones machine where you have to install all this. It may even be cheaper to use a plan where all this is pre-installed, since in that case the hosting company has an easier time monitoring the server because it's a standard setup.
Whether web hosting company will provide this mail server
Most Java hosting plans will include this. Not the very cheapest ones, but anything that's around $15/month or more will include a mail server.
You may wish to look at a few different hosting companies, just to get a feel of what they offer and charge: http://faq.javaranch.com/java/ServletsFaq#hosting