After some more experience I found that there are basically 3 approaches:
- Modify the .udd files that OllyDbg uses to store comments directly.
- Use a label plug (unfortunately the one I found does not work on 2.01)
- Create a debug file in a format OllyDbg understands (DWARF I think)
Since 3 is pretty complex, my best option is probably 1.