There are several different ways you can go about learning a social dance, and since many people I know either are learning or are thinking about learning, I figured I'd throw out my tips.
(Social dance refers to, in this case, structured partner dancing in an informal or non-competition format - salsa, swing, and tango are good examples. Learning to dance competitively is an entirely different thing.)
Know that the awkward stage passes.
Almost everyone is awkward or awful at it at first. That's fine. You have to keep working at it. And even the most horrible, awkward dancer can become a beautiful dancer with enough practice and determination.
Eventually - and this is when things get really fun - you stop having to think about it. Your body just does what it's supposed to. Things happen that are awesome, and you didn't consciously think about doing them. That sort of dance nirvana is the reason why dancers keep coming back, but it doesn't happen your first time out. Or your second. Or maybe not for the first year(!). But all of the time investment is totally worth it when it does. I promise. You just have to get there.
Do it regularly, and make an effort to keep improving what you know.
This is often not a problem for people who have truly been bitten by the dance bug. But lots of people, for whatever reason, only attend a dance class or event every so often, and then wonder why they don't improve. You have to make a certain amount of commitment to it, and you can't simply be satisfied with what you've already learned. The best dancers (the best anything, really) are the ones who are continually striving to be more than what they already are. Don't quit going to classes once you think you're "good enough." There's no such thing.
Ask people to dance. Specifically ask people who are better than you.
Most newbies are terrified to do this. It's understandable - you don't want to embarrass yourself too badly, so you dance with another newbie or with no one at all. Or you're afraid of getting turned down, or of the pity dance.
However, the way I learned (and the way most people learn) is by dancing with someone better than you are. Especially if you dance with them on a regular basis, you'll probably start closing the gap pretty quickly.
Also, just because you're inexperienced doesn't mean people can't have fun dancing with you. All of us remember learning, and probably have some more experienced dancers that we owe our ability to. Most people are willing to pay it forward.
Alternately, don't *just* dance with people better than you.
One of the best things I've heard in a lesson is to be grateful for a difficult partner. Anyone can learn a move with someone who's good - but not everyone's good, and not everyone's going to do it perfectly the first time. Learning how to do something well even with a difficult partner means you've really learned it.
Stay for the actual dance.
Many new people stay for the lesson and then book it after the real dancing actually starts. I feel like you learn at least as much, if not more, on a real floor in a real situation. You'll never be able to perfect your dance moves while in the sterile and structured environment of a class, and the longer you stay away from the "social" part of social dance, the harder a time you'll have feeling comfortable there. And the less comfortable you are, the less likely you are to dance well.
It's a social dance.
That means you dance with several different partners. If you try to stick just to your significant other, you're missing most of the point of the activity. You get yourself into a rut, and it limits your abilities and your confidence significantly - if you can only dance with one other person effectively, you're not really a dancer. Besides, learning how to interact with all different kinds of people will make you even better when you *do* dance with your significant other.
Additionally, the social part doesn't apply just to the dancing - talk to people when you're sitting on the sidelines. People you've talked to are more likely to want to dance with you.
Social dance is not a dating service.
If you're looking for a dating service, try a dating service. I hear match.com and eharmony.com work pretty well. However, the point of dancing is dancing. Lots of people end up dating people in the dancing community (although I'm not one of them, and am glad of it), but it's incidental, not the objective.
Don't be prejudiced based on appearances.
You can have a very enjoyable dance with all sorts of people. Remember - it's a dance, not a date. Physical attraction to the other person is not a necessary part of the equation, even though you're doing a physical activity.
Experiment with different instructors.
People often seem to stick to a single dance teacher, usually the one they started out with. Different instructors have different things to offer, and one might teach something in a way that works better for you. There are so many different styles and approaches to the same move or the same dance, and taking what you like from different teachers is a good way to broaden your perspective.
That said, working consistently with one instructor, once you've found one you like and who understands you, is incredibly beneficial. Just don't settle for the first teacher you come across, get frustrated, and give up.
Don't learn a bit and start thinking you're a hot shot.
Hubris is a downfall. If you've only been dancing for a short amount of time, you're probably too ignorant to know how bad you really are. There's very little, for me, that's more off-putting than someone who lectures other dancers, who scoffs at other people, who generally thinks they're way better than they are. Socrates said it quite well: "The only true wisdom is in knowing you know nothing."