When I reapply to universities which have previously rejected my applications, do I have to pay application fees again?
Generally, there is nothing special about a reapplication; you apply just as if you were applying for the first time.  You will submit all the required materials again.  Of course, you will submit updated transcripts and scores, and you will probably have revised or rewritten your application essay, so you'll submit the updated version.  Letters of recommendation will also need to be resubmitted; you should ask your letter writers to update their letters to reflect whatever you have been doing in the last year.  And yes, you do have to pay another application fee.

Most institutions will give your new application a fresh look; the fact that you have previously applied and been rejected should not prejudice them against your current application.  (However, people are human, and if some of the same people are still on the admission committee, they may have some memories of the weaknesses they saw in your previous application.)

Of course, to have a better chance of acceptance this time, you should have made yourself a stronger applicant!  Hopefully you have better GRE scores and stronger letters of recommendation, and can report some additional helpful and relevant coursework or work experience in the year since your last application.