(Long response)
CK,
A couple of comments and thoughts.
First, if you are halfway through reading GTD, I'd recommend reading it all the way through before you start implementing. I actually read it through twice before I started doing anything.
Some of the little things that DA suggests do, for whatever quirky reason, work. When I did my first mindsweep, I followed the suggestion of writing each thought, idea, project, etc. on a separate sheet of paper. I went through 3 legal pads doing it. But it was worth it when I moved to processing. One big benefit was that doing so made it easier to maintain my mental focus on one thing at a time. If you're just listing them out (30 to a page or so), you might find that processing takes more effort.
You mentioned that not all of your ideas have verbs; that's probably ok. Essentially at this stage you're just brainstorming and getting all of those thoughts and ideas off your mind and into a written form that you can later put into a trusted system. Later, when it comes to defining and identifying projects, you probably will want to start each with verbs. Jason Womack has a great list of verbs here:
http://www.davidco.com/forum/viewtopic.php?t=510 There are a couple of other shorter verb lists posted elsewhere here.
Your next step (if you are still collecting) is processing. You asked whether software or paper methods were better. You won't find an answer to that here, because the answer depends on you: how do you best recognize and associate information. If you choose a paper method, DA has a great setup here:
http://www.davidco.com/tips_tools.php?id=25 And if you prefer a palm-based method, DA advises how he's set it up here:
http://www.davidco.com/tips_tools.php?id=43
Finally, how to best associate next actions with projects again depends on you. DA and others do so mentally: you can put enough information in your description of a next action so that you mentally associate it with a project. "Email Sandy" might become "Email Sandy re request for additional support staff." The weekly review ensures that you are regularly reviewing everything often enough to ensure that things don't slip through the cracks and that steps are being taken on projects.
Others take additional steps to associate next actions with projects and with project plans. For Palm-based people, some prefer ShadowPlanner, while some prefer LifeBalance.
Again, I'd suggest reading the whole book before you try to implement. Others might disagree, but I personally found it much easier to go through the initial collect-process-organize steps once I understood what the end goal was.
A final thought: At a certain point, you just need to jump in. I mentioned that I read the book twice before I did. I also bought and read Ready for Anything first, read and digested every article on the Tips and Tools page on this site, and read what seemed like every post on the discussion boards before I actually took the plunge. I read one person's comment that said something like "The best thing you can do is stop trying to learn more about this, and just start implementing it." (I can't find the original post to give proper attribution; whoever said it, please take credit.) I read that, and implemented the following weekend. Did I do it perfectly? Heck no. But I've been refining my approach and life just feels better.
Congrats on starting. You'll never look back.