My interpretation of your question is that the payments are already recorded in CiviCRM. I am also assuming you can have some way of searching for the contacts who have paid membership fees but have no membership. (If not, edit your question to make that clear and I will amend my answer accordingly).
Once you have obtained a list of the contributions (via an Advanced Search displaying results as contributions or a Find Contribution search) you should export the results. You will need at least the contact id, and probably the date of the payment (which I assume will become the start date for the membership).
Create a CSV for importing that contains at least the contact Id, the membership type and the membership start date (refer to the Import Membership section of http://book.civicrm.org/user/current/common-workflows/importing-data)
Import the membership file (Memberships > Import Memberships )
Note: this will create memberships for the contacts, but the memberships and the contributions will not be linked. That linking cannot be done via the GUI.
As a suggestion, next time it may be more efficient to send people the URL for an online membership page so that the membership is created at the time the payment is recorded.