It goes without saying that the real first step is learning about GTD. The best way to learn it is to pickup a David Allen GTD book and go through it at least twice. You should plan to re-read it at least once a year as a refresher.
Once you understand GTD, it's time to get started and the first thing you will need is a way to make a list. The most time consuming startup task is dumping everything from your brain to paper. This step means you will likely become unavailable to the world for a day and dump. You will have to go through past meeting notes, your email and calendar system, and anything else where you may have made commitments.
Once you have dumped everything you can onto into your massive list, it is important to continue adding items regularly. Use your capture system to capture to dos immediately and then periodically go through your capture system and move the items through the GTD process.
I use my weekly review to move items through the GTD process and to capture anything I may have missed.
The biggest stumbling block to getting started with GTD is this first initial big brain dump. People get overwhelmed thinking about everything they have to capture. They worry about forgetting important things so they just find excuses to not get started. For me, this is a great reason to get started.
Remember that once you have everything listed down, you can then tackle each one individually and decide what it is, and how you should handle it. A much more zen way to handle the process of time management.