I was going to try for 'Going from Private to General' or something like that for the title, but I don't want snark to get confusing.
I've gotten this question a few times, in person, in forums, in comments, etc. It's a question that I have to think back to, and I honestly can't remember exactly which deck was my first. I'm fairly sure it was Jund-colored, and I know I eventually settled on Adun Oakenshield, but it wasn't always creature-centered as it is now.
Let's go over the steps. You may be an old hand at this, but I'm trying to compress a lot into a small space.
Step 1: Exposure
You're at a store, or with some friends, and someone asks, "Who wants an EDH game?" You're curious, since that's a variation you haven't really heard of or know a lot about. GO ASK. If someone's playing it, then they are likely to be a fan. There aren't many people who simply 'tolerate' a format like this and also have a deck.
If the person you ask about it is like me, they may say a lot in a very short amount of time. The principles of Commander are pretty straightforward: Build a deck around a general, no duplicate cards aside from basics, and don't be a jerk. (That last part is open to local interpretation, and that's cool.)
Watch a game, maybe someone will loan you a deck--I'm notorious for that--and play it like any other game. Feel the infection take root.
Step 2: Intrigue
I do remember that the idea of 'no duplicates' really appealed to me when I first heard it, but it took me six months and seeing a game to appreciate the brilliance fully. You're building a 99-card deck, with singleton everythings. There's a lot of chaos involved, and if you want every game to play out the same way (as often happens in Constructed) then you're going to be disappointed.
Indeed, Sheldon's articles were once titled, "Embrace the Chaos" which is such a ridiculously great tagline that I wish I could steal it.
You're going to go home and think about EDH. You're going to wonder what cards you'd play, what colors you would play, and this step may involved frantic phone calls or emails to those who introduced you to this.
At this point, you're likely to throw together some good cards in 2-3 colors, pick a fun general, and take your deck for a spin. Your results will likely be disappointing, but hopefully you are undaunted.
Your first deck should be built in one of two ways: You're going to pick a general you think is fun, and add cards of the appropriate colors, or you're going to choose your favorite spells/colors, then pick a general who matches that.
(The first deck is 99% going to be one of those things, based on my conversations with others)
Step 3: Obsession
This is where the roller-coaster really takes off. You're going to quickly learn that in EDH, you can play lots more expensive spells, things that were last picks in draft are now all-stars, and any old foils you have laying around may be worth serious money. You visit mtgcommander.net, and hopefully join those forums.
At this point, you're gaining an insight into how a deck can be built around a general, or how a general can merely be the accessory to a deck's plan. About this time, you've decided to build a tribal deck, or a theme deck.
Building EDH decks is addictive for players who have a long history with the game. We can remember all sorts of cards that looked like fun but were no good for the formats of the time. If you have a thorough collection still, you may start building EDH decks by riffling through boxes, taking out fun cards in a color, and having a first draft of a deck that is 400 cards.
It is possible that you look up decklists online and immediately look for 'staples' and 'must play' cards. I can't advise against this strongly enough. Build your deck as well as you can, and then go play it. When you are trading with someone, mention your general and how you're looking for fun things to add. I know that I LOVE to talk ideas with someone when I'm trading, and I always enjoy making suggestions.
Step 4: Tinkering
This is a very fun step. No EDH deck is perfect. No deck is ever 'finished'. You will build a couple of decks, to give some variety, and constantly think about what is and isn't in the deck.
Now, you can determine the relative power level of the decks you're playing with. You don't want to have the consistently best deck in the room, with a win rate in the 90% range, because that leads to you getting killed like it's a game of Archenemy. You don't want your deck to be the weakest in the room either.
It's a key part of enjoying the game to have your deck be at nearly the same level of shenanigans as the rest of the decks at the table.
Some tables, everyone has lots of tutors and infinite combos. Some tables, no one plays Wrath effects.
There's two approaches to deckbuilding:
1) Have a variety of decks, with varying levels of silliness. I favor this approach, since I can choose which deck to play and try to fit in with any group.
2) Only play with the same people over and over. This has a certain appeal, with the right people. However, you'll be in for a shock when you venture out.
Step 5: Contentment
Eventually, you'll weep, for there were no more generals to build around. You'll reach a zenith of understanding both the format and its spirit. This is where your playgroup/local store can be a real treasure, because while your deck is a well-tuned machine, everyone else's deck is a valley full of sand, gum, and corrosive acid. That's where the fun lies in the chaos--your deck will play differently depending on your opponents.
Step 6: Spread
That's right, now you get to tell other people how awesome this format is! I've told many people that if EDH had been around ten years ago, a LOT of players would still be in the game. It's a format that doesn't require a lot from you--it's very possible to build a deck that's pretty strong without going into mountains of debt.
I liked writing this. I'm very likely to come back and tweak it...like it's a deck!