With dedication you could learn to climb at a top-rope or bouldering climbing gym without professional instruction. The key skill there is belaying, and you could learn that from videos. However I would never recommend this route if good instruction is available. You may have difficulty separating Internet know-it-alls from experts, therefore you may not know if you are following wisdom or nonsense unless you get professional instruction. While learning from an experienced climber may help, there are also a lot of experienced climbers with bad safety skills, so having survived X years of climbing is really no proof of good fundamentals. At the very least gyms usually offer a one-session intro class that teaches how to belay, put on your harness, tie in, etc.
If you wish to do real (outdoor) climbing you will want both instruction and someone experienced to climb with; there are simply too many things you don't know you don't know in my opinion. The books I've read don't cover everything, and some things just can't be learned from that medium anyway. Rather than "hiring a guide" I recommend that you find a rock climbing course. Vet the instructor. I took one at a local community college and I was fortunate enough to get a very good instructor, but I know that some people who took a course at the same place a few years before I did learned techniques that my instructor would have failed, saying they were deprecated by the AMGA over 20 years ago.
Books lay things out in an organized and systematic form that you can easily reference. How to Rock Climb! by John Long was required reading for the first climbing course I took, and I haven't seen a better book of the same type.
Blackbear asked:
I'm wondering what your opinion would be on what gear to buy first and what gear to possibly rent? I'm a bit hesitant to go out and buy all new gear if it turns out that we're not good at it, or don't end up liking it. As far as I can tell, buying a harness, shoes, belay device, chalk bag and some locking carabiners would be a good first step. Is climbing rope generally supplied in climbing gyms?
Shoes
If you have an interest in climbing and no nagging injuries that would make it painful or difficult I simply can't imagine you not enjoying some style of climbing. It takes a while to figure out what climbing shoes should feel like, but honestly I would just buy the first pair from REI so that you can return them if they don't work out or you realize they are the wrong size. I chose to use rental shoes and I got a nasty case of nail fungus for the first time in my life; it ended up costing me a lot more than new shoes would have.
Fit to the shape of your foot is most important. It doesn't matter how "good" a shoe is if it doesn't fit you right, and feet vary a great deal, so don't look at what other people are wearing as a guide. You want a shoe that feels like it was vacuum molded to your foot: zero gaps anywhere, but not compressive. In other words "fits like a glove" or as close as you can get. Some shoes stretch very little, some stretch quite a bit, so you won't really know how a shoe will fit until you've worn it for a while. I highly recommend buying from a place that lets you return them even after they are worn, rather than guessing they will stretch and fitting them too tightly. Good climbing is usually about using your feet well rather than hauling yourself up with your arms, and you won't use your feet well if they hurt; avoid that.
Top-rope or Bouldering
You'll want to decide whether to start with bouldering or top-rope climbing. I recommend top-rope, but I'm a scaredy-cat and like the safety of a top-rope. Ideally I think you should start out on top-rope to safely learn fundamentals and good footwork, and to give your tendons and ligaments time to strengthen. Muscle grows faster than connective tissue; injuries are common for those who push too hard right from the start. Avoid hang boards and other training devices in your first year of climbing; you'll build both strength and skill by actually climbing, and do it more safely. (Excessive focus on strength may cover bad technique; this is probably why girls often seem to learn faster than guys.) After perhaps six months of top-rope climbing switch to indoor bouldering for a while to build power and additional skills. After that you should have a sense of the kind of climbing you want to do and a decent foundation for whatever direction you choose.
If you have an athletic foundation and don't mind a little risk you may prefer (indoor) bouldering. (You could e.g. dislocate an elbow or break a wrist if you fall wrong, even with pads.) There you'll only need shoes; you can improvise a "chalk pot" or the gym may provide one.
If you choose top-rope look for harness packages that include a belay device and belay carabiner (also known as an HMS carabiner) and sometimes a chalk bag; you'll usually save a bit of money this way. (As you will by getting last year's model on closeout.) The Black Diamond Momentum package is a popular choice. Don't spend a fortune on a harness; the very light and expensive ones are for competition climbers and won't make a lick of difference to you, other than possibly being less comfortable. (An exception is if you are doing mountaineering and want a low-profile harness to fit under a hip belt, as my instructor explained, but I have no experience with that yet.) Learn to belay with an ATC or other "tube-style" device (my preference is the Black Diamond ATC-XP); a "Gri-Gri" or other such device will only lead to bad habits at this point and cost far more.
I have never heard of a gym where you bring your own rope for top-rope climbing, so yes, they are provided. (You'll need a UIAA certified Dynamic rope for lead climbing but you aren't ready for that yet.) A number of gyms even have auto-belay devices now which let you climb without a partner; it is an auto-braking system that lowers you slowly when you fall off. If you climb on an auto-belay make sure you do an extra safety check since you won't have a partner to catch mistakes like putting your harness on wrong!
Safety
Make sure all your safety equipment (harness, belay device, carabiners, etc.) is properly certified. Look for a logo like this:

Be aware that there are counterfeit climbing goods in existence so buy only from reputable sources.
Carefully read all of the instruction booklets and labels that come with your gear; they will warn you against various kinds of misuse that could kill you, such as improperly loading a carabiner or using bleach on your harness. Make sure that you are using all equipment as intended. (For example there are climbing ropes that are meant to be used only in pairs; the booklet should make this clear even if an incompetent sales person does not.) If a piece of gear does not come with a booklet contact the manufacturer for this information; every piece of gear I have purchased has come with such a booklet.