What do I have to do to add a hostname? For example I have foobar.com and would also like to have media.foobar.com.

Do I just mess with some files on the server? Or do I need to mess with the nameservers? Or even some settings with the "domain company" it self?

Without knowing how to do it I'm imagining that if I want media.foobar.com to be created and directed to <ipaddress>:81 I just add to /etc/hosts: "<ipaddress>:81 media.foobar.com", with "<ipaddress> foobar.user.openhosting.com foobar localhost" already present.

The hosting and the domain are not with the same company.

You need an A (or AAAA for IPv6) record in the DNS zone file for the domain. So it is the nameserver, yes. If someone else is hosting your DNS, they might have a web interface that will allow you to make the necessary changes (GoDaddy has this, for example).

I believe you need to talk with your hosting vendor and ask them for it. I've done several times and usually there is a web interface that will allow you to add subdomains.

Greetings

Alejandro