Webmaster - configurar dns para correo

Tengo un dominio, con las dns configuradas para que el tema web funcione perfectamente.... pero como configuro las dns para poder poner un servidor de correo ?

Podrías aclarar si el servidor es tuyo y lo tienes que configurar, (si es asi tambien el SO), o si es un servidor gratuito o de pago, o si solo has pillado un dominio
Salu2