WordPress.org

Where is data stored?

In an array in the wp_options table. Just one record regardless of the number of find and replace rules.

Will the find and replace slow my site?

Unless you're using 50+ rules, you shouldn't notice any performance impact.

What does the regex checkbox do?

You can do a straight up find and replace where the plugin will look for an exact match of what you specified. You can also used advanced pattern matching that is available through regular expressions by checking the regex checkbox.