The functions get_site_option, update_site_option, delete_site_option and add_site_option can be used to write settings valid in all network.
My plugin User Security Tools makes use of this functions.
(http://wordpress.org/extend/plugins/user-security-tools/)
This functions are in wp-include/functions.php
This is a great help. Definitely steered me in the right direction.
For anyone else looking to accomplish the whole register_settings thing on a multisite I definitely recommend the mentioned plugin for guidance. I also took a quick look based on what you said and found a neat tutorial:
http://wpengineer.com/2324/register-settings-on-wordpress-multisite/
edit: Just to clarify this is used instead of the register settings.
Thanks for the help!
So for multisite plugins, you don’t use the Settings API?