Help! Noob Question

Do I need to add the new domain to my own web hosting first before connecting it here, for email hosting?

Nope, no need for that.

I should add as a second answer:

While not necessary, having a website at the domain can improve your inbox delivery. I have witnessed spam filters at third party services that judge a mail domain for having no website.

And I would like to add that having a newly registered domain can also decrease delivery. I know the service we use at our company takes this into the mix.