Could someone please explain me how the brute force attacks on my ssh server are supposed to work? Ssh still asks for a password even though the username is unknown. That would mean that the attacker, when going through his alphabetical list of usernames, won't know if any of the usernames was correct or not. That again would mean that to successfully gain access through a brute force attack he would need to go through all possible usernames combined with all possible passwords, wouldn't it?

That would take a zillion tries and a lot of time, so why are people still bothering to attack my box for ten minutes, going through the alphabetical list once, and then stop? Can they deduce usernames somehow or are they just plain stupid?

These sorts of attacks don't really concern themselves with going through all possible combinations of usernames and passwords because that is just plain stupid. Instead, they tend to go for obvious combinations. Most machines are going to have a user root, so that is one to try along with obivious passwords like toor or password. These sorts of attacks really depend on the user being careless and not using strong passwords. The fact that these sorts of attacks persist suggest that such careless users are depressingly common.

try fail2ban if they annoy you.. I love opening my email each day to see 10 more ip's banned

That again would mean that to successfully gain access through a brute force attack he would need to go through all possible usernames combined with all possible passwords, wouldn't it?
Yes, for a true brute force,that's how it works. Which is why brute force attacks are not very effective against systems that have username/passwords that are reasonably random and include numbers and punctuation. However, if you allow "root" to login directly over ssh, then the attacker will know the most important username on the system...root.

That would take a zillion tries and a lot of time, so why are people still bothering to attack my box for ten minutes, going through the alphabetical list once, and then stop?
Exactly. Which is why these attacks are only effective against systems that have very poor passwords, like root/root, admin/admin, etc. Technically most of the attacks you'll see are called 'dictionary attacks' and use a list of words of phrases rather than iterating through letters like "aaaaaa" to "zzzzzz" (really it would be "a" to "zzzzzz").

Can they deduce usernames somehow or are they just plain stupid?
No, they can't deduce usernames (other than "root"), but what they *are* looking for are lazy or stupid administrators who use bad passwords.