RV Permission Set
The easiest way to give your users access to Record Validation is with the Record Validation Permission Set. The advantage of using the RV Permission Set is that it is updated automatically whenever new classes, tabs etc are added to RV. This means you don't have to make any changes after future RV updates where new classes might be introduced.
However, with the RV Permission Set users have access to all of Record Validation, including the settings in RV Setup. If needed you can deny your users access to certain RV 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 Record Validation.
If, upon installation of Record Validation, you chose to install for Administrators only, all access to RV Apex Classes, RV Objects etc. was added to the standard 'System Adminstrator' profile. This means that if a new Record Validation 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.