To be clear, automatic forwarding (as you seem to be describing it) is often done via the mail server itself and specific steps vary from program to program.
Do I have to host my own mail server?
Not necessarily. You can use third-party solutions. These mail services are provided by either the registrars themselves or other companies in a manner similar to web hosting (i.e. they run the mail server for you). These companies will often provide instructions on how to forward mail with their services (as you have discovered through your research).
The problem is [even after searching], I still don't know how to setup such a domain email.
Mail servers are like web servers in that they typically use a domain name (e.g. mail.example.com) which points to their public IP address. These domains, in turn, are placed in the DNS records for your primary domain (e.g. example.com) as Mail Exchanger (MX) records. These MX records are what others use to find the mail server(s) for your domain. Any user creation or forwarding is done at the server level.
As above, "primary domain" below means e.g. example.com.
Go through any service setup process with the third party, as necessary.
Place whatever mail domain names your provider gives you (e.g. mx1.mailhost.com, mx2.mailhost.com) as MX records into the DNS records for your primary domain.
Create your accounts (e.g. firstname.lastname@example.org, etc.) via your service provider.
Forward mail as detailed by your service provider.
Note that using registrar-based services typically negates the first two steps above.
Download a Mail Transfer Agent (mail server) and configure it to recognize mail for your primary domain. Follow the steps for your software.
Setup a domain in your DNS records (e.g. mail.example.com) to point to the IP of your mail server (as you would for a normal website).
Place your custom mail server domain name(s) (above) as MX records into the DNS records for your primary domain.
Create your accounts (e.g. email@example.com, etc.) via your mail server interface.
Forward mail as detailed by your mail server software instructions.
[Which mail server] would suite my situation?
Almost all mail servers support automatic forwarding to other addresses. There are both free and paid solutions on various platforms. If you want free and are on Windows, I might personally recommend hMailServer. If you are on Mac, I believe there is a basic "Mail" service. For its part, Linux generally come with one or more mail servers (such as Sendmail) depending on distribution.
Which DNS records are needed?
For receiving mail, MX records are all that are needed.
For sending mail, you technically do not need any special DNS records. However, relating to spam prevention, there are a number of records you will potentially wish to have. These include:
These can all be required depending on the recipient (whomever you are sending mail to). In practice, SPF records are likely to matter most and Reverse Pointer records should be created anyway. DKIM is a part of many (especially US) sites that process mail, while Caller-ID for Email is (arguably) the least important of the four.
In any case, if you lack these records, the response is up to the receiving mail server. They may accept the mail (and likely filter it more heavily) or they may reject it. If you are getting mail returned (especially as spam), these records are a good thing to check.