Apparently I have a problematic GTX580 video card.
I followed instructions somewhere and installed Ubuntu 12.04 using "nomodeset". Then I logged into recovery mode, got the updates, also initiated "nvidia-current" package.
The problem is I now get black screen instead of desktop (after normally logging in) like 30% of the time. It is quite odd especially when I don't know what key combination to press in that situation - I just mash my buttons and computer restarts soon (maybe CTRL+ALT+DEL causes it?). At other times everything is fine, actually I am smoothly typing this message using that very same Ubuntu.
How should I deal with this problem? How to act when I see a black screen? Maybe there are error logs somewhere?