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.
Setup Overview
As above, "primary domain" below means e.g. example.com.
Third-party Services
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. user@example.com, 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.
Self-hosting
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. user@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.
1"Do I have to host my own Mail Server?" - Yes; "If yes, which one would suite my situation? - You choose the mail server you like the best; "If yes, which one would suite my situation?" - They all would allow you to setup forwarding to an email provider like Google or Outlook; "Which DNS records are needed?" - This is well documented. What does your research indicate? – Ramhound – 2017-12-06T16:26:27.720
After googling for 3 hours now I have only found websites explaining how to do this using a web-frontend offered by some registrars, and a IBM website which is about configuring DNS records for Emails - but it doesn't explain such a simple thing as forwarding. – nickkoro – 2017-12-06T18:00:16.190
Typically whichever mail client you install on the server so you can check your mail allows you to setup forwarding rules. Otherwise you can also use CPanel (other similar tools) to configure the email forwarding rules for you. How you do it exactly depends on the mail server you selected. – Ramhound – 2017-12-06T18:22:41.050