Where should I store global data for my multi-site WordPress plugin?

You’re looking for get_site_option(). From the Codex:

Retrieve option value based on name of option. In multisite, return network option, blog option otherwise.