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.