They are stored in the options table in the normal WordPress database.
You should always export a backup of your quick redirects (from the plugin options page) as they are just stored as an array in an option field in WP. If something happens during an update and it does not correctly write the array to the options table, you will loose them all (as with any array that is not correctly stored). Then the only way to restore them at that point is a database restore.
So after you get them back from your backup, go export a copy of them and put them someplace you can easily find them if you have an issue in the future.
Additionally, it is a lot easier to add a lot of redirect from the export file than typing them in one at a time as well.
Warm regards,
Don
