Damn! Twitchy mouse finger. 
Was going to suggest that you look for an adult education course in reupholstering – local high school, community college, places like that. Reupholstering is easy enough, but there are a lot of tricks that are easier to learn by being shown instead of having to work them out yourself. On top of that, in a class you can share supplies/tools, instead of buying everything. Unless you plan to do all the rest of your furniture or take it up as a trade or something, you really don’t need to have 4/5ths of a carton of brads left over and so forth.
Anyway, a few answers:
Yes, take off the old tattered fabric. Not only are you likely to be able to feel (or even see) the edges of holes through the new material, but it also helps you: pay attention to the order as you take sections off, use them as rough patterns for your new pieces, and then install the pieces in reverse order to removal.
If the batting is extremely lumpy, or smelly (mildew, smoke, dog whiz), or infested with god knows what, or has chunks missing – basically, if it is bad shape of any kind, take it off. If it’s pretty much intact, just sort of compressed and beaten down by use, you can leave it and put new layer(s) over.
Before you put any time at all into the project: Sit on the couch and bounce up and down a bit: comfortable? seem sturdy? Then turn the item over and take off the dust cloth on the bottom, and take a good look at the springs/coils/strapping. If they aren’t in good shape, pass the job along to a professional. Also, pick up one corner of the couch and try to twist it (as in, warping the couch frame long way, not pivoting around another foot on the ground…) If the frame flexes appreciably, or if creaks a lot or make popping noises or in any way seems flimsy, ditch the idea. Reupholstering is only worth the trouble if you have a structurally sound couch that is of a size/shape that suits you.
You need staples long enough to do hold. As in, hard wood vs. soft? How thick is your fabric/padding layer(s)? Try what you have on hand, and move up or down in size as needed. The brand of staple gun doesn’t matter, so long as it fits your hands and you are strong enough to squeeze it repeatedly.
What else do you need? Tack strips, probably. Welting if you like the look of that. Ornament tacks if you want them for emphasis. Fringes and bullion and tassels and edgings and whatever you want for adornment. The fancier the result you want, the more doodads you need to buy. Oh - you’ll also need a sewing machine to hem the skirt and to make seat cushion covers.
Time it takes: depends on fanciness and your experience. The first thing I did was a loveseat, with self-welting, a box pleated skirt, and a plaid fabric that took careful matching.-- That took about 7 weeks, but only a couple hours each week. (That was my “classroom project” as I took a night course.) Next I did a quick and dirty job on a couch for my sister’s college apartment, where nitpicky perfection didn’t matter. I did that one with no ornamentation, no skirt, leaving the old material & batting, and just wrapping the existing seat cushions in another layer or two of batting. I knocked that one off in a single fairly long day.
BTW, be kind to yourself and pick a forgiving fabric for your first time. That is, either a solid or some small all-over non-directional print. Definitely no stripes/plaids!
Strength needed: well, some staple guns take a lot of hand strength to squeeze. Outside of that, help in shifting the couch around sometimes as you work on it is nice but not necessary. An extra pair of hands to help hold something taut while you nail or staple is nice, but again, not necessary.
Best advice: just take it slowly and work step by step. Upholstery is very forgiving. If you ‘finish’ covering an arm and it looks wrinkly or too loose to you, pull the staples out carefully then stick the piece on again, pulling it tighter that time.