1)To set up a mail server you need a server (share hosting or dedicated server).
All the hosting companies offer you a "Control panel" software which helps you to manage your web server. You can configure your domain names, firewall, ftp, etc... and your mail server
It is extremely easy to add or remove some email accounts. Even if you have some issues, any serious web hosting company has a support team 24h/7 who will help you in less than 1 hour to configure it.
2)Once you created your email accounts, you have to add them in your mail client software (Outlook, Opera mail, etc...). How to do that? Well just type in google "How to configure name_of_your_mail_software
". You will find tons of tutorials.
3)You need to improve the reputation of your IP/domain names.
Mail companies like Gmail, Hotmail, Yahoo, mail.com, Aol, etc.... check the domain name (and ip) of the sender. I will not explain you here everything about this topic. You will find a great article about that here:http://emailmarketing.comm100.com/email-marketing-ebook/flagged-as-spam.aspx
If you plan to send mailing, it is better to have your own dedicated server instead of a share server. Because with a share server, you share the ip of the server with other webmasters. So if another webmaster make a SPAM, the ip of your server will be black listed.
You can check the ip of your server here:http://mxtoolbox.com/
I hope my answer could help you or someone else.