Идея хранилища состоит в том, чтобы предоставить вашему коду одно место, куда они могут пойти, чтобы получить данные из некоторого постоянного хранилища (большую часть времени из вашей базы данных). Ваша бизнес-логика будет на другом уровне.
Хранилище может предлагать простые функции создания, чтения, обновления и удаления (CRUD) или более конкретные функции для извлечения или обновления данных.
Другими шаблонами, которые вы можете посмотреть, являются UnitOfWork (пример этого - ObjectContext, используемый в Entity Framework) и шаблоны проектирования Layering, которые показывают, как отделить код доступа к данным от вашего бизнес-кода.
Вы уже упоминали об отделении интерфейса от реализации. Кодирование интерфейса также является хорошей практикой.
Здесь вы можете найти больше информации. PEAA также содержит другие отличные описания шаблонов проектирования и способы их использования.