I have created a module in K2 that displays the titels of all items.
I want to order these items by category.. How can I do this?

There are several choices for ordering in the mod_k2_content.
If you select only one category just above the ordering choices, you will get what you want
When you select more than one category, categories will be mixed.
I would suggest trying to create more than one mod_k2_content module first as this will be simpler than adding another ordering query.