First, a semantic (but important) quibble: You do want to do "usability testing" not a "focus group." Focus groups are for researching markets and discovering subjective tastes in a target group of people. You're not interested in opinions, you're interested in facts, most importantly "what makes my signup process difficult"
jms mentioned hallway testing and that's a great place to start. I doubt you'll need to even get to the point where you need to do more formal testing (eg, video cameras, screen recording software, formal script) but that avenue definitely exists.
Steve Krug's book "Don't Make Me Think" (Amazon) has a great chapter (ch 9) on how to do testing. There should be plenty of resources online. The key term you're googling for is going to be "usability testing" along with "informal" or "hallway"
The specific questions from your post:
"Should I do it in person": Yes, absolutely.
"I imagine having 15-20 people ... ": You probably don't need this many people. Most usability issues are uncovered with 5-10 people. You can get away with as few as 3 if you notice the first 3 people all encountering the same issues.
"Do I need to pay people?": Maybe. If you can afford to, its a good idea. It makes things feel more professional, and encourages people to actually show up :) For informal testing though, it isn't required.
The basic idea is that you are observing (not interviewing) people in order to find specific, factual, actionable issues (not necessarily subjective feelings) with your interface. To that end:
Figure out what task (focus on tasks and goals, not just "screens") you want the users to perform.
Tell your users, in plain english, without leading, what do to. For example "Ok, so you've decided you want to play this game, can you please do whatever you feel you need to do to start playing." If people aren't understanding that they need to create an account, don't tell them "Ok, create an account!" Don't have tasks like "ok so now click the create account button" - that button might not be obvious. Again, focus on goals not actions
Don't tell the users what do to, don't take control of the computer. Your goal is to be as invisible as possible. If the user asks you a question, a good response is "Pretend you're at home and I'm not here. Only let me know when you're so frustrated with the software that you would pick up a phone to call support.
You're not conducting a scientific experiment. Its perfectly acceptable if each user does different things, or if the environment isn't controlled. All you care about is collecting pieces of the puzzle.
It doesn't really matter who you test with, as long as they're not familiar with your product.
Once you think you've found enough "blocking" issues, stop testing and fix the issues. Repeated testing after you have a problem is only going to uncover the same problem over and over. Instead, fix and then re-test. Its better to do more rounds of testing with fewer people than one big test with lots and lots of people.
You do not need people to "talk aloud" and explain their every action. Just watch what they're doing. If you're confused about WHY they did something, stop and ask them if you think they won't remember why later. You can integrate these questions into a "test script"
Always debrief after the test. Keep in mind that people will generally rate things more favorably than they actually were (both to be nice to you, and because people remember successes and forget failures).
Remind people that you're testing the software, not them. Be patient and polite, especially in hallway testing where you're not paying them. If you recruit people in advance, you should probably pay them. If you use cash (don't bother with checks), have receipts prepared. Gift cards for a local retailer (jamba juice, starbucks, etc works well). At this point you'll also want a quick participant agreement form. Professional firms pay anywhere from $75-200 (and more, for specialists like doctors) per hour for testing but you can get away with less if you're just meeting people in a library meeting room.
If, after you've done all this you realize you need a larger scale study, you can look at hiring specific firms to do it - it is, however, pretty expensive ($5000 minimum for a competent firm I'd guess). Again, chapter 9 of "Don't Make Me think"