Hmm, okay. Since the Session Tutorial said that we can use server-side-session management (= No cookies) I thought that this is what I was doing. So I'm wrong here, correct? I don't want any cookies. And I do have a separate login page.

Ok, you can consider this a follow up to Re^4: Problems with session expiration (there is no session)

no cookies means no session ;

$session->header sends cookies

if you don't want cookies, you can communicate the session id through link rewriting, like "/sessionid/link" or "/link?sessionid" or "/link?id=sessionid"

or through hidden form field ... but then all your links have to be buttons

your code as written doesn't actually do this

A session is just an id associated with a browser, browser communicates sessionid to server via cookie/urlparam/formparam .... server looks up sessionid in database (or wherever) to retrieve data associated with sessionid

is that clearer?

Another alternative to cookies is Digest access authentication which is just another HTTP header (like cookies)
Mojolicious::Plugin::DigestAuth - HTTP Digest Authentication for Mojolicious
Plack::Middleware::Auth::Digest - Digest authentication

Catalyst::Plugin::Session::Manager::Client::Rewrite - handle sessonid with rewriting URL
Catalyst::Plugin::Session::State::URI - Use URIs to pass the session id between requests

Good luck

Thanks everyone. :)
I basically wasn't aware of how it really works. Basically I seem to had two problems.

1) Using "new CGI::Session();" didn't work for me.
According to CPAN Perl uses the 'applications default directory' for storing session information. I think that this most likely is a directory from Apache. Since my webspace is on a hoster and I have no direct access to the server I cannot check whether I am allowed to write there or not.
Therefore I created a new directory in the root of my webspace to store the sessions in and adjusted the "new CGI::Session();" command with the new path. Same for the CGI::Session->load(); commands.
Since it's working with this I guess that I'm not allowed to write into that default directory.

2) My login_check module was using my self-written function that prints the navigation and everything else on my website. And it does that without adding session information. Right now I'm using simply "print $session->header();" to print out the header. But I think that I'll get around this. :)

As an extra it is advised to use "$session->flush();" to make sure that the session information is actually written to disk on the server. Not sure if I really need it or not but it doesn't hurt.