I'd have to agree with LovelyIsabella. Start with private lessons. Most studios, at least around here, seem to offer a free introductory private lesson; it shouldn't cost anything to at least get some sort of feel for what it's like.
The first time I tried to start learning how to dance, I enrolled in a group class and didn't feel like I was getting it at all. That and a severe imbalance in the male/female ratio in the class (group classes around here almost always have too many men, and in the class in question several women dropped out after the first session) was enough to put me off the whole idea.
When I got the itch to try again, I went to one of the beginner nights at my local studio and was lucky enough to be snared into a free private lesson by one of the teachers. That made all the difference -- I felt like I learned twice as much in that initial one-hour lesson as in the four hours of group class. That was just under a year and a half ago and I've been hooked ever since.
That said, I've since observed that some people learn a lot better than others in a group class or workshop. Unfortunately for my budget I've found that group classes -- and I've since taken them at a few studios, so I'm pretty sure it's me -- just aren't all that effective for me in general. The only time group class material has really stuck for me is when I've gone over it with my teacher afterwards, and at that point I may as well have had the teacher show it to me to begin with. Other people can see a pattern once or twice and immediately do it themselves. (I envy those people.)
But even if you're great at picking up patterns, I also think that people who start off with lots of group classes tend to pick up some bad habits that are tough to shed later on. Especially their leading and following technique. In most group classes both partners know exactly what the pattern or sequence is supposed to be and there's no need to lead or follow it well. Some instructors try to emphasize lead and follow in their group classes, but without actually dancing with the students there's not much they can do at the beginning level.
In my opinion (speaking as a purely social dancer, I should say) learning the fundamentals of leading and following is astronomically more important than learning patterns, and it's the biggest reason to take private lessons right from the get-go as a beginner. I've been complimented for my clear lead more times than I can count, but only a few times for dancing a wide variety of patterns. On the flipside, as a leader I'd far rather dance with a good follower who doesn't know many patterns than with someone who knows lots of patterns but gives me nothing to work with.