yo uso phpmailer.
En el host que contratas te proporcionan un servidor smtp con numero de puerto, host etc.. los datos necesarios para poder enviar mensajes.
Revisa la documentación de phpmailer, pones los datos correspondientes.
y no tendría que haber ningún problema.
http://www.desarrolloweb.com/articulos/phpmailer.html 