That's awesome! Climbing is one of the most enjoyable and rewarding activities, as well as one of the best workouts imaginable. (I have wanted to quit while lifting weights, I have never wanted to quit while on a wall).
The best place to start is just going to your local climbing gym, renting some shoes, and climbing.
Rock climbing, in the beginning, is not the complex thing that people imagine. Sure, when you get to harder routes, technique, body positioning, use of gear, etc. will need to be mastered, but at the beginning, nothing is more important than just showing up and having fun.
I have had the pleasure of teaching a dozen, or so, of my friends how to climb and every single one initially viewed rock climbing as something “difficult.” Naturally they tried to pull themselves up easy routes with brute arm strength, when they would never climb a ladder this way. Relax, let your legs do most of the work, and don't over-extend yourself unless you need to.
If you enjoy climbing at its most basic form, than you will get to a point where you want to progress beyond scrambling up easy rock walls. When you get to that point, take a class at the gym in top rope climbing. When you crave more than that, take a class in lead climbing. When you have been stuck at a certain level of difficulty and you know that you need better technique to improve as a climber, take a class on technique or (as I try and do with people both more and less skilled than me) get tips from other people in the gym. Climbers usually just enjoy climbing, and making friends means making potential climbing partners, so people are typically friendly and helpful.
The only piece of gear that is required are climbing shoes (all gear is rentable, but $5 for shoes every day?). I HIGHLY recommend intentionally avoiding “better” and “more expensive” shoes. Climbing shoes tend to balance comfort with grip. Entry level shoes will allow you to climb all day in comfort, while still giving you a good foothold on 90% of the routes in a gym (100% at a beginner's level). More expensive, technical, shoes will sacrifice comfort, and contour your feet in unnatural ways (extreme downturn) in order to find grip in places that you won't encounter for years. Budget around $100 for shoes.
When you're ready to start top rope climbing, you'll need a harness ($50), a locking carabiner ($10), and a belay device ($20). But I would invest in those when it's time to top rope. You may find that you love bouldering and never get the urge to rope up.
So, to sum up: Go for it! It's a great sport. Just show up, do it, and you won't regret it.
One other thing, I'm sure there are videos on youtube. I learned technique from a DVD before I ever started climbing in a gym. While this may be helpful, all gyms have their own standard of safety. Ask. By all means, learn from every possible source, but don't assume that because you saw a guy say that a certain knot is safe, that you can use that knot in a gym. Gyms often require extra precautions and for very good reasons.