As Wizards takes books out of print, I feel like we need an answer here that gives updated information on how to get started with 4e and where to go to get those resources. Some products are still readily available from online retailers like Amazon. But mostly, those are starting to dry up and in the coming years we will see mostly digital distribution for 4e rules and content.
First and foremost, if you are not ready to spend any money, Wizards is now providing quick start 4e rules and Keep on the Shadowfell as a free adventure via Drivethru. I've played through Keep and while it's not the best adventure ever, it is designed to show off D&D quite well. This was the first adventure published for 4e and it stands as somewhat iconic to the game. It's been updated a bit since first publication to reflect the rules changes, but there are additional fixes to it discussed here that do improve it.
With the Redbox supplies dried up and no hope of a reprint with 5e coming out this summer, the best bet for getting started is probably this particular package. If you like the game and are interested in continuing, investing in the books would be the next step. Choose your line, I expect the balance of the publications to be offered digitally as stocks run out at retailers. All of Wizards' 4e digital publication offerings can be found here.
As far as what set of books make a complete game, we still have the same two options:
The original line:
- Players Handbook
- Dungeon Master's Guide
- Monster Manual
The first book in each of these series are still available at the time of this answer, I will update if they become unavailable for a long period of time. MM 2 and 3 are available online through drivethru, and I expect the balance of the library will become so as stock runs out.
OR the Essentials line:
- Heroes of The Fallen Lands/Heroes of the Forgotten Kingdoms
- Dungeon Master's Kit
- Rules Compendium
- Monster Vault
Both the first and second players books are still available on Amazon right now, as are the Monster Vaults. However, the RC and DMK are both hard to find and available via Drivethru.
Any answer here would be incomplete without mentioning Wizards' in house digital tools. This is a great investment if you decide to play 4e regularly. They have a character builder, voluminous compendium, and numerous free adventures, player advice and other articles of interest to D&D players distributed exclusively to subscribers. It does cost money, but the time effort that the character and monster builders will save you (in addition to the cost of books saved by the compendium) does have a significant value (I feel like I've gotten my money's worth). More information about DDI here.