Нужно хранить данные в базе данных и не просто базе данных, а желательно в базе данных фонового процесса. Например, я сам всегда использую IndexedDB, он удобен тем, что там можно хранить что угодно - любой тип данных.
P. S. Есть риск потерять данные, если юзер очистит полностью историю и кеш или переустановит расширение. Если нужна высокая надежность, можно данные и вовсе хранить у себя на сервере, либо предлагать функцию экспорта и импорта данных специальным файлом настроек. Насчет chrome.storage ничего не могу сказать, никогда не пользовался им.
