For the Multi-level Navigation plugin I simply give users the option to either use their theme to provide the CSS or they can add the CSS directly into their admin panel and that is then dynamically added to a stylesheet within the plugin. So the data is either stored in the users theme or in the database, whichever they choose.

Or if a theme is designed to work with the plugin, then the plugin detects the presence of a compatible theme and automatically relies on the themes CSS file (although this can be overridden).