Where do I start? I don’t have much money, and the idea of swiveling hips in a group is intimidating, to say the least.
I have been told it is good exercise, I am hoping it will be easier on my knees that a lot of other dancing, and it would be just plain cool to be able to say “I can bellydance” 
Has anyone learned successfully, or at least tried to learn? Please share your trials, tribulations, and methods!
If I remember correctly Zayda enjoys belly dancing.
I don’t really know if she does vanity searches, but if she does, that should help.
Good Luck on your quest.
Sorry. Vanity searches only work if the name is spelled correctly. Hey Zyada! 
Check your community bulletin boards.
A real class is a good place to start. The teacher can verify that your posture is correct so you don’t do yourself an injury. Trust me, in a beginner class, everyone else will be where you are, a little intimidated at first, then loosening up and starting to have fun.
I’ve taught for … dang, off and on, maybe 11 years? It is very good exercise, and if you’ve got knee or back problems, SUPERIOR exercise. I’ve got terrible knee problems, and as long as I don’t get into some ethnic foot stomping or try to do too much floor work, I’m golden. Plus, if I’m dancing a lot, my knees are more stable, because it works the small muscles around them much more. Heck, my sister taught me, and she started belly dancing after some major knee damage, IIRC.
There are a few videos worth checking out. For general exercise, Veena and Neena’s videos are pretty good. Not a lot of posture talk, though. Try zilltech.com - that’s my sister’s site (she’s a major pro, I’m very minor, non-pro other than teaching locally). Her listing of videos and music is superior, and that’s not just sibling talk.
Try http://www.zilltech.com/VideoStore.html
But I still think a teacher is your best bet for starting.
I just started this year (as did a friend of mine, with a different teacher) it’s surprisingly non-intimidating in a group. Or, at least, class #2 wasn’t intimidating.
I haven’t “learned” yet, but I’m having fun, I’m fooling myself into thinking my abs are stronger, and it’s fun to go and watch.
This was a really good book, I read it when I first started and it might help alleviate some of your nervousness.
My wife has been belly dancing for over three years now. She takes classes through the local community center. She really enjoys it, says the classes are not at all intimidating, that it’s not hard on the knees and it’s very good for the abs. (I can vouch for that last one.)
I myself have now been to several dance recitals and a (not uncommon) misconception that I had was that belly dancing is about being hot and showing off your body – most of the professional dancers are normal looking, older women. If anything, a little heavier than average. But they can belly dance like you wouldn’t believe – belly dancing really well takes a lot of skill and muscle control. So, although it can be a very seductive dance, one should never assume belly dancing is only for the young and nubile.
I definitely recommend going with an instructor. www.shira.net is a good resource for finding instructors and other BD related stuff. If you are in a large enough area to have your choice of several instructors, I recommend that you go to a couple of restaurants offering live dancing to see some of the local dancers. This will give you an opportunity to see if there is one style you like over another. Once you see a dancer you like, ask her if she teaches, or if not, who her teacher is.
If you don’t have any local instructors or can’t afford the classes, you can get videos and you may even be able to check books out of the library. I learned my first moves from a book, and I think it actually helped me with some of the technique.
For videos, the Neena and Veena video is quite popular right now and from what I hear is a good intro to the dance.
I hate it when I think of a good joke when it’s too late…
I’d say learning some of the moves from a book gave me a hip up on other students.
I am no expert in bellydance, but my wife has a video that she uses for a workout thing, which is Dolphina, Ultimate Goddess, or something like that. Can’t find the tape at the moment, but from what I’ve seen, it looks like a pretty good tutorial on bellydance.