The absolute best way to start playing D&D is with a good DM. That goes for playing any role playing game, quite frankly. The system actually doesn't matter... if you have a good DM, you could jump right into the most complicated system in the world and find it a breeze, since part of the DM's job is to make things easy for new players. 1st edition, 2nd, 3rd, 3.5, 4th, Pathfinder... doesn't matter as much as the DM if you're the player. The DM should be able to help you make a character, asking simple questions to define what you want and filling in the details for you. After that, play is simply a case of imagining the world he tells you about and telling him what you do. He'll tell you what dice to roll to see if you succeed at stuff, and your sheet will tell you anything extraordinary that you can try to do.
So, your first step should be to try to find a game with open spots. Right now I'm running a game, but I'm full up for players... more than 5 players and things start getting bogged down, so I don't like to do it. I understand that Wednesday evenings (I think at 6pm?) there's a D&D Encounters group, which is basically a pickup game sort of thing where you can walk in, make a character in a few minutes (with the DM's help), and start playing right away. I'm not 100% positive they're still going on, but last I heard it was still going strong.
However, if after some searching you cannot find a game, the next thing to do is start one yourself. This is going to take a bit more work. On the other hand, DMing can be one of the most rewarding pass-times around, and the hobby ALWAYS needs new DMs. And everyone has to start somewhere-- not everyone can join a game first.
When you're starting to become a DM, edition DOES matter. Here, I
would recommend 4th Edition, because it's almost certainly the easiest to DM for. It combines the "Make stuff up" strength of 1st edition with the easy math of 3rd edition, and then makes the math even simpler by getting rid of cascading dependencies.
The traditional way of starting out with a brand new set of players and DM, where
everyone is new, is to pitch together to buy the three core books, but 4th edition makes it even easier. Buy a set of dice (you'll want at least 1d4, 3d6, 1d8, 2d10, 1d12, 1d20, and later on each player may want to buy a set for themselves) or even splurge for a
pound of dice (support our FLGS, ask them to order it for you), and then download wizard's
Quick Start Rules and Adventure, and get a feel for things. It's not the full game, but it's plenty to start learning with, and it's free to do (aside from buying the dice, which you'll need anyway).
The quick start rules will tell you the rules for how to run a Combat Encounter, and will give you pre-built characters for 1st and 2nd level. And then the sample adventure will give you the monsters and setting to get started... take note, as DM, you should consider even at this early engagement to change the adventure to fit your own imagination. Use the rules, and the monsters, and then make stuff up. In addition to the quickstart rules, you'll want some graphpaper and pencils-- you'll be drawing your gameboard and drawing where everything is. You might find it helpful to use coins as tokens.
Soon, once you've gotten the hang of things, you'll want to have more monsters to send at your players, and your players will want to customise their characters, and even level up past level 2. It's time for you and your players to pitch together and buy the following three books:
Players HandbookDungeon Master's GuideMonster ManualIn 4th edition, note that there's also sequels to the above books, so you may find a Player's Handbook 2, a Monster Manual 2 and 3, and so on and so forth. Don't get those yet until you're comfortable with the game more.
The Players Handbook will enable your players to make new characters that are different from the pre-built ones you got for free. The Dungeon Master's Guide will give you LOTS of good advice for how to run a game, as well as provide additional rules for how to run different kinds of encounters. The Monster Manual will give you the enemies for your players to fight.
If you want, you can buy those books right from the get-go, but you may find yourself overwhelmed if confronted with making a character before you know what combat is like, so even if you do so, I highly recommend downloading the quickstart rules anyway for the characters. But otherwise, the books are good, and will definitely show you what to do step by step.
After you've been playing a bit more, you'll want to spruce things up. Start looking into more books... the Monster Manual 3 is particularly good, for instance. Also check out the miniatures on the stores walls... using little figurines for your players and the monsters they face can really add enjoyment to the game.
Any questions?