DC Permission Set
The easiest way to give your users access to Duplicate Check is with the Duplicate Check Permission Set. The advantage of using the DC Permission Set is that it is updated automatically whenever new classes, tabs etc are added to DC. This means you don't have to make any changes after future DC updates where new classes might be introduced.
However, with the DC Permission Set users have access to all of Duplicate Check, including the settings in DC Setup. If needed you can deny your users access to certain DC pages.
Profile settings, custom permissions
Another option is to grant your users user access via profile settings or a custom permission set. Note that profile settings and custom permissions need to be updated manually whenever a new class, tab etc. is added to Duplicate Check.
If, upon installation of Duplicate Check, you chose to install for Administrators only, all access to DC Apex Classes, DC Objects etc. was added to the standard 'System Adminstrator' profile. This means that if a new Duplicate Check release contains new classes, tabs etc, the System Administrator profile needs to be given access to those. New classes, tabs etc. are listed in the Release Notes.
Profiles and permissions in Salesforce
Users can have only one profile but, depending on the Salesforce edition, they can have multiple permission sets. You can assign permission sets to various types of users, regardless of their profiles. See Salesforce's 'Manage Data Access' page for more information about profiles and permission sets in Salesforce.